題目
#

leetcode 211 - Design Add and Search Words Data Structure (題目說明請點連結)

題目簡述
#

設計一個資料結構，支援新增單詞和搜尋單詞兩個操作。搜尋單詞時，單詞可能包含點號 .，其中每個點號可以匹配任何一個字母。
例如，搜尋 "a.c" 可以匹配 "abc"、"adc" 等單詞。

範例
#

Example 1:

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

Example 2:

Input
["WordDictionary","addWord","addWord","search","search"]
[[],["a"],["a"],["."],["a"]]
Output
[null,null,null,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("a");
wordDictionary.addWord("a");
wordDictionary.search("."); // return True
wordDictionary.search("a"); // return True

解題思路
#

這題要求我們設計一個支援新增單詞和搜尋單詞的資料結構，其中搜尋操作支援萬用字元（點號）。我們可以使用Trie（前綴樹）來儲存單詞，並使用深度優先搜尋（DFS）來處理包含點號的搜尋。

解法
#

使用 Trie 資料結構來儲存所有新增的單詞
實作 addWord 方法：將單詞插入到 Trie 中
實作 search 方法：使用 DFS 來搜尋單詞，處理點號萬用字元
當遇到點號時，嘗試所有可能的字母路徑

步驟
#

Trie 結構：
- 創建 TrieNode 類別，包含子節點陣列和單詞標記
- 使用 26 個子節點來表示英文字母 a-z
新增單詞：
- 遍歷單詞的每個字符，在 Trie 中建立或遍歷節點
- 在單詞結尾標記 isWord = true
搜尋單詞：
- 使用 DFS 來搜尋單詞
- 當遇到點號時，嘗試所有可能的子節點路徑
- 當遇到普通字母時，沿著對應的子節點路徑搜尋

例子說明
#

插入單詞 “bad” 和 “dad”，搜尋 “.ad”

(root)
 ├─ b
 │   └─ a
 │       └─ d (isWord=true)   ← "bad"
 └─ d
     └─ a
         └─ d (isWord=true)   ← "dad"

操作	單詞	路徑	結果	說明
addWord	“bad”	root → b → a → d	成功	插入單詞 “bad”
addWord	“dad”	root → d → a → d	成功	插入單詞 “dad”
search	“.ad”	root → (任意) → a → d	true	點號匹配 ‘b’ 或 ’d’

搜尋過程說明：

搜尋 “.ad”：
- 第一個字符是點號，嘗試所有可能的子節點
- 嘗試 ‘b’：root → b → a → d，找到 “bad”
- 嘗試 ’d’：root → d → a → d，找到 “dad”
- 返回 true

完整程式碼
#

java

// Trie 節點類別
class TrieNode {
    TrieNode[] children = new TrieNode[26];  // 子節點陣列，長度為 26（英文字母 a-z）
    boolean isWord = false;                  // 標記是否為完整單詞
}

class WordDictionary {
    private TrieNode root;  // Trie 的根節點
    
    // 建構函數，初始化 WordDictionary
    public WordDictionary() {
        root = new TrieNode();
    }
    
    // 新增單詞到 Trie 中
    public void addWord(String word) {
        TrieNode node = root;
        
        // 遍歷單詞的每個字符
        for(char c : word.toCharArray()){
            int idx = c - 'a';  // 計算字符在陣列中的索引
            
            // 如果字符對應的子節點不存在，創建新的子節點
            if(node.children[idx] == null){
                node.children[idx] = new TrieNode();
            }
            
            // 移動到子節點
            node = node.children[idx];
        }
        
        // 標記最後一個節點為完整單詞
        node.isWord = true;
    }
    
    // 搜尋單詞是否存在於 Trie 中
    public boolean search(String word) {
        // 使用深度優先搜尋來處理包含點號的搜尋
        return dfs(word, 0, root);
    }

    // 深度優先搜尋方法
    public boolean dfs(String word, int index, TrieNode node){
        // 邊界條件：如果節點為空，返回 false
        if(node == null) {
            return false;
        }
        
        // 邊界條件：如果已經搜尋到單詞結尾，檢查是否為完整單詞
        if(index == word.length()) {
            return node.isWord;
        }

        char c = word.charAt(index);
        
        if(c == '.'){
            // 如果當前字符是點號，嘗試所有可能的子節點路徑
            for(TrieNode child : node.children){
                if(child != null && dfs(word, index + 1, child)){
                    return true;
                }
            }
            return false;
        } else {
            // 如果當前字符是普通字母，沿著對應的子節點路徑搜尋
            int idx = c - 'a';
            return dfs(word, index + 1, node.children[idx]);
        }
    }
}

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

時間複雜度
#

時間複雜度：
- 新增操作：O(L)，其中 L 是單詞長度
- 搜尋操作：O(26^L)，其中 L 是單詞長度（最壞情況下，所有字符都是點號）
空間複雜度：O(26^L)，其中 L 是最長單詞的長度
- 每個節點最多有 26 個子節點
- 需要儲存所有可能的前綴組合