#211 Add and Search Word - Data structure design

實作一個資料結構，可以加入單字和搜尋單字。 直覺就是用Trie，這題跟一般的Trie的差異是， 可以search("b..")，表示b開頭的3個字母的單字。

Concept:

Add word和Trie相同， Search word和一般搜尋不同的是，"."沒有指定字母， 所以就要把所有children都檢查一遍看有沒有單字存在裡面。 這邊就需要用到backtracking了。

Implementation: 可以用recursive來實作， input為字串char array, int k 作為指目前到字串的第幾個字母, TrieNode node為目前所在的TrieNode。 終止條件是當k已經到char array的最後， 此時return node.isWord。 如果當前的char非"."，就檢查該children是否有存東西、再繼續找下一個字母。 如果當前的char是"."，就要檢查所有children，看是否有存東西、再繼續找下一個字母。

Code:

public class WordDictionary {
    /*
    Concept:
    Trie
    */
    public class TrieNode{
        char val;
        TrieNode[] children;
        boolean isWord;
        public TrieNode(char val){
            this.val = val;
            children = new TrieNode[26];
            isWord = false;
        }
    }
    TrieNode root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode(' ');
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode cur = root;
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
            if(cur.children[c-'a']==null){
                cur.children[c-'a'] = new TrieNode(c);
            }
            cur = cur.children[c-'a'];
        }
        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) {
        return match(word.toCharArray(), 0, root);
    }

    public boolean match(char[] chars, int k, TrieNode node){
        if(k==chars.length) return node.isWord;
        if(chars[k]!='.'){
            return node.children[chars[k]-'a']!=null && match(chars, k+1, node.children[chars[k]-'a']);
        }else{
            for (int i = 0; i < node.children.length; i++) {
                if (node.children[i] != null) {
                    if (match(chars, k + 1, node.children[i])) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

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