力扣 211 添加与搜索单词 - 数据结构设计

题意：添加与搜索单词

思路：

1. 在添加单词的适合，构建TrieNode
2. 在搜索的时候，分成.和char不同情况，递归搜索

思想：Trie

复杂度：时间O（n)，空间O(n)

class Node {
    public boolean isLeaf;
    public Node[] next = new Node[256];
    public char cur;
    public Node(char cur) {
        this.cur = cur;
    }
}

class WordDictionary {
    Node root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node(' ');
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        Node temp = root;
        for(int i=0;i<word.length();i++) {
            char cur = word.charAt(i);
            if(temp.next[(int)cur] != null) {
                temp = temp.next[(int)cur];
            } else {
                Node t = new Node(cur);
                temp.next[(int)cur] = t;
                temp = t;
            }
        }
        temp.isLeaf = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return find(word, root, 0);
    }
    
    boolean find(String word, Node temp, int index) {
        if(index == word.length())
            return temp.isLeaf;
        char cur = word.charAt(index);
        if(cur == '.') {
            for(int i=0;i<256;i++) {
                if(temp.next[i] != null && find(word, temp.next[i], index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            if(temp.next[(int)cur] == null)
                return false;
            return find(word, temp.next[(int)cur], index+1);
        }
    }
}