211. Design Add and Search Words Data Structure

Medium

Description

設計一個資料結構，支援 addWord(word) 新增字串和 search(word) 搜尋字串。搜尋時 . 可以匹配任意一個字元。

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]

Intuition#

核心思路：Trie + DFS 回溯。一般字元走固定路徑，遇到 . 時嘗試所有 26 個子節點。

addWord 與標準 Trie 插入完全一樣
search 的難點在於 . 萬用字元：需要嘗試所有可能的子節點
遇到 . 時用 DFS/回溯遍歷所有非 null 子節點

Approaches#

1: HashSet with Pattern Matching#

概念: 用 HashSet 儲存所有字串，搜尋時用正規表達式匹配。簡單但效率低
時間複雜度: O(n * m) - n 為字串數量，m 為搜尋字串長度
空間複雜度: O(n * m) - 儲存所有字串

class WordDictionary() {

    private val words = mutableListOf<String>()

    fun addWord(word: String) {
        words.add(word)
    }

    fun search(word: String): Boolean {
        val regex = Regex(word.replace(".", "."))
        return words.any { it.length == word.length && regex.matches(it) }
    }
}

⭐2: Trie + DFS Backtracking#

概念: 用 Trie 儲存字串。搜尋時逐字元走 Trie，遇到 . 則對所有非 null 子節點進行 DFS
時間複雜度: O(m) 一般情況，O(26^m) 最壞情況（全是 .）。m 為搜尋字串長度
空間複雜度: O(T) - T 為所有插入字串的總字元數

class WordDictionary() {

    private class TrieNode {
        val children = arrayOfNulls<TrieNode>(26)
        var isEnd = false
    }

    private val root = TrieNode()

    fun addWord(word: String) {
        var node = root
        for (ch in word) {
            val idx = ch - 'a'
            if (node.children[idx] == null) {
                node.children[idx] = TrieNode()
            }
            node = node.children[idx]!!
        }
        node.isEnd = true
    }

    fun search(word: String): Boolean {
        return dfs(word, 0, root)
    }

    private fun dfs(word: String, index: Int, node: TrieNode): Boolean {
        if (index == word.length) return node.isEnd

        val ch = word[index]

        if (ch == '.') {
            for (child in node.children) {
                if (child != null && dfs(word, index + 1, child)) {
                    return true
                }
            }
            return false
        } else {
            val child = node.children[ch - 'a'] ?: return false
            return dfs(word, index + 1, child)
        }
    }
}

DFS 搜尋時要注意提前剪枝：子節點為 null 就跳過。如果搜尋字串中 . 很多，最壞情況會變成指數級，但實際應用中通常 . 不會太多。

補充：按長度分組的 HashSet 優化

將字串按長度分組儲存在 HashMap<Int, MutableList> 中，搜尋時只需比對相同長度的字串。

class WordDictionary() {

    private val wordsByLength = HashMap<Int, MutableList<String>>()

    fun addWord(word: String) {
        wordsByLength.getOrPut(word.length) { mutableListOf() }.add(word)
    }

    fun search(word: String): Boolean {
        val candidates = wordsByLength[word.length] ?: return false
        return candidates.any { matches(it, word) }
    }

    private fun matches(s: String, pattern: String): Boolean {
        for (i in s.indices) {
            if (pattern[i] != '.' && pattern[i] != s[i]) return false
        }
        return true
    }
}

🔑 Takeaways#

Pattern: Trie + DFS 是處理「帶萬用字元的字串搜尋」的標準組合
關鍵技巧: 遇到確定字元走確定路徑，遇到萬用字元展開所有可能。這個模式也出現在正規表達式引擎和檔案系統的 glob 匹配中