[LeetCode刷題筆記] 211 - Add and Search Word

題目描述：

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.

一刷題解（Trie）：

這題整題實現上與一般的字首樹沒甚麼區別，Add也是照樣的遍歷字符串每個字符，依次加到字首樹中；一般字符的Search也是通過遍歷字首樹中對應的字母子節點進行檢查。比較特殊的是，這題容許輸入’.’，代表「任意字母」。

這就代表我們在遍歷過程中，每遇到一次’.’，都要對26個子節點下各自的所有子節點進行檢查。這樣一來，常規的在Search方法裡遍歷就無法滿足需求了，我們需要通過利用遞歸進行深度優先查找去得到我們的結果。

public class WordDictionary {

    TrieNode root;
    bool canFound;

    public WordDictionary()
    {
        root = new TrieNode();
        canFound = false;
    }

    public void AddWord(string word)
    {
        TrieNode curr = root;
        foreach (char c in word)
        {
            if(curr.children[c - 'a'] == null)
            {
                curr.children[c - 'a'] = new TrieNode();
            }
            curr = curr.children[c - 'a'];
        }
        curr.isWordEnd = true;
    }

    public bool Search(string word)
    {
        TrieNode curr = root;
        canFound = false;
        SearchHelper(curr, word, 0);
        return canFound;
    }

    //遞歸查找
    void SearchHelper(TrieNode node, string word, int idx)
    {
        if (canFound || node == null) { return; }
        if (word.Length == idx)
        {
            if(node.isWordEnd) { canFound = true; }
            return;
        }
        //遇到'.'的字符時，需要對26個子節點進行檢查
        if(word[idx] == '.')
        {
            for (int i = 'a'; i <= 'z'; i++)
            {
                SearchHelper(node.children[i - 'a'], word, idx+1);
            }
        }
        else
        {
            SearchHelper(node.children[word[idx] - 'a'], word, idx+1);
        }
    }
}

public class TrieNode
{
    public TrieNode[] children = new TrieNode[26];
    public bool isWordEnd;
    public TrieNode()
    {
        isWordEnd = false;
    }
}