208. Implement Trie (Prefix Tree)

解題思路

看題目敘述直接想到之前寫過的 208. Implement Trie (Prefix Tree)，所以直接拿那題的程式改改看。

Node class 跟 addWord 直接複製貼上，而 search 需要修改。兩題差別在於要思考遇到 . 要怎麼辦，其實就是找當下節點底下有哪些路徑，全走過一遍找看看，所以會需要重複呼叫函式。進一步改寫後就變 dfs 了。

程式碼

class Node{
public:
    bool isEnd;
    Node* child[26];
    Node()
    {
        isEnd = false;
        for(int i=0; i<26; i++)
            child[i] = nullptr;
    }
};
class WordDictionary {
public:
    Node* root = new Node();
    WordDictionary() {
        
    }
    
    void addWord(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                current->child[word[i] - 'a'] = new Node();
            current = current->child[word[i] - 'a'];
        }
        current->isEnd = true;
    }
    bool dfs(Node* root, int start, string& word)
    {
        Node* current = root;
        for(int i=start; i<word.size(); i++)
        {
            if(word[i] == '.')
            {
                for(auto child : current->child)
                {
                    if(child != nullptr && dfs(child, i+1, word))
                        return true;
                }
                return false;
            }
            else if(current->child[word[i] - 'a'] == nullptr)
                return false;
            current = current->child[word[i] - 'a'];
        }
        return current->isEnd == true;
    }
    bool search(string word) {
        return dfs(root, 0, word);
    }
};