題目在問什麼

要設計一個資料結構，支援兩件事：

  • addWord(word)：加入單字
  • search(word)：查詢單字是否存在

其中 search 的字串可能包含 '.'，代表這個位置可以匹配任意小寫字母。

例子

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]

解題思路

這題非常適合用 Trie。

原因很直接：

  • addWord 本來就是逐字往下建立節點
  • 一般 search 也是逐字往下走
  • 唯一麻煩的是 '.'，因為它代表任意字母

一旦遇到 '.'，就不能只往單一路徑前進，而是要對當前節點的所有可能子節點繼續搜尋。

為什麼需要遞迴

如果 search 中沒有 '.'，Trie 查找就是單一路徑。

但有了 '.' 之後，搜尋會在某些位置分岔，所以最自然的寫法就是 DFS：

  • 普通字母：往指定子節點走
  • '.'：把 26 個子節點都試一次

只要其中一條路能成功走到單字結尾，就代表搜尋成功。

代碼

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)
    {
        canFound = false;
        SearchHelper(root, 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;
        }

        if (word[idx] == '.')
        {
            for (int i = 0; i < 26; i++)
            {
                SearchHelper(node.children[i], 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;
    }
}

複雜度

  • addWord：O(n)，n 是單字長度
  • search：一般情況 O(n)，但若包含很多 '.'，最壞情況會分岔成較大的搜尋樹

這題先記住的重點

  • 這題本質是 Trie 的進階版搜尋
  • 難點不在 addWord，而在 '.' 造成的分支搜尋
  • 遇到 wildcard 時，用 DFS 去展開所有可能路徑是最自然的做法