🌕 211. 添加与搜索单词 - 数据结构设计

难度: 🌕

问题描述

---

解法

class WordDictionary {
    // 思路：
    // 构造 26 叉树，对于包含 . 的单词，查询所有在非空子树
    Node root;

    public WordDictionary() {
        this.root = new Node('a'); // 虚拟头结点
    }
    
    public void addWord(String word) {
        Node cur = root;
        int len = word.length();
        for(int i = 0; i < len; i ++) {
            char c = word.charAt(i);
            int index = c - 'a';
            if(cur.child[index] == null) {
                cur.child[index] = new Node(c);
            }
            cur = cur.child[index];
        }
        cur.end = true; // 标记终止
    }
    
    public boolean search(String word) {
        Node cur = root;
        int len = word.length();
        return searchAtIndex(word, len, 0, cur);
    }

    private boolean searchAtIndex(String word, int len, int index, Node cur) {
        // 递归终止条件
        if(index == len) {
            return false; // 下面的逻辑判断，保证了根本不可能到达这里
        }
        
        // 
        char c = word.charAt(index);
        if(c != '.') {
            int i = c - 'a';
            if(cur.child[i] == null) {
                return false;
            }
            if(index == len - 1) {
                return cur.child[i].end; // 说明是最后一个字符，判断是否是末尾节点
            } else {
                return searchAtIndex(word, len, index + 1, cur.child[i]);
            }
        } else {
            // 说明是 . 可以匹配任何字符，查找非空子节点
            for(int i = 0; i < 26; i ++) {
                if(cur.child[i] != null) {
                    if(index == len - 1) {
                        // 最后一个字符，只需要判断子节点是否是终止点即可
                        if(cur.child[i].end) {
                            return true;
                        }
                    } else {
                        if(searchAtIndex(word, len, index + 1, cur.child[i])) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }
}

class Node {
    char val;
    boolean end;
    Node[] child;
    public Node(char val) {
        this.val = val;
        this.end = false;
        this.child = new Node[26];
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

---

输出