Trie

Add and Search word -Data Structure design

• Trie的经典题型，熟练掌握

class WordDictionary {
    class Trie {
        Trie[] children;
        boolean isWord;
        public Trie() {
            children = new Trie[26];
            isWord = false;
        }
    }
    Trie root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Trie();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        char[] arr = word.toCharArray();
        Trie cur = root;
        for (int i = 0; i < arr.length; i++) {
            Trie[] children = cur.children;
            int idx = arr[i] - 'a';
            if (children[idx] == null) {
                children[idx] = new Trie();
            }
            cur = children[idx];
        }
        cur.isWord = 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) {
        char[] arr = word.toCharArray();
        return match(arr, 0, root);
    }
    private boolean match(char[] arr, int start, Trie cur) {
        if (cur == null) return false;
        if (start == arr.length) {
            return cur.isWord;
        }
        char ch = arr[start];
        if (ch == '.') {
            Trie[] children = cur.children;
            for (int i = 0; i < 26; i++) {
                if (match(arr, start + 1, children[i])) {
                    return true;
                }
            }
            return false;
        } else {
            cur = cur.children[ch - 'a'];
            return match(arr, start + 1, cur);
        }
    }
}