0211. 添加与搜索单词 - 数据结构设计【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 字典树 + DFS

1. 📝 题目描述

• leetcode

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配。

实现词典类 WordDictionary ：

• WordDictionary() 初始化词典对象
• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false。word 中可能包含一些 '.'，每个 . 都可以表示任何一个字母。

示例：

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

---

提示：

• 1 <= word.length <= 25
• addWord 中的 word 由小写英文字母组成
• search 中的 word 由 '.' 或小写英文字母组成
• 最多调用 10^4 次 addWord 和 search

2. 🎯 s.1 - 字典树 + DFS

c

typedef struct WordDictionary {
    struct WordDictionary* children[26];
    bool isEnd;
} WordDictionary;

WordDictionary* wordDictionaryCreate() {
    return (WordDictionary*)calloc(1, sizeof(WordDictionary));
}

void wordDictionaryAddWord(WordDictionary* obj, char* word) {
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!obj->children[idx]) obj->children[idx] = wordDictionaryCreate();
        obj = obj->children[idx];
    }
    obj->isEnd = true;
}

bool dfsSearch(WordDictionary* node, char* word, int i) {
    if (!word[i]) return node->isEnd;
    if (word[i] == '.') {
        for (int k = 0; k < 26; k++) {
            if (node->children[k] && dfsSearch(node->children[k], word, i + 1))
                return true;
        }
        return false;
    }
    int idx = word[i] - 'a';
    if (!node->children[idx]) return false;
    return dfsSearch(node->children[idx], word, i + 1);
}

bool wordDictionarySearch(WordDictionary* obj, char* word) {
    return dfsSearch(obj, word, 0);
}

void wordDictionaryFree(WordDictionary* obj) {
    for (int i = 0; i < 26; i++) {
        if (obj->children[i]) wordDictionaryFree(obj->children[i]);
    }
    free(obj);
}

js

var WordDictionary = function () {
  this.children = {}
  this.isEnd = false
}

/**
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
  let node = this
  for (const ch of word) {
    if (!node.children[ch]) node.children[ch] = new WordDictionary()
    node = node.children[ch]
  }
  node.isEnd = true
}

/**
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
  function dfs(node, i) {
    if (i === word.length) return node.isEnd
    if (word[i] === '.') {
      for (const key in node.children) {
        if (dfs(node.children[key], i + 1)) return true
      }
      return false
    }
    if (!node.children[word[i]]) return false
    return dfs(node.children[word[i]], i + 1)
  }
  return dfs(this, 0)
}

py

class WordDictionary:
    def __init__(self):
        self.children = {}
        self.is_end = False

    def addWord(self, word: str) -> None:
        node = self
        for ch in word:
            if ch not in node.children:
                node.children[ch] = WordDictionary()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            if word[i] == '.':
                return any(dfs(child, i + 1) for child in node.children.values())
            if word[i] not in node.children:
                return False
            return dfs(node.children[word[i]], i + 1)
        return dfs(self, 0)

• 时间复杂度：addWord 为 $O(m)$，search 最坏 $O({26}^m)$，其中 $m$ 是单词长度
• 空间复杂度：$O(T)$，其中 $T$ 是所有插入单词的字符总数

算法思路：

• 使用字典树存储单词，addWord 与普通 Trie 插入相同
• search 时遇到 . 需要遍历当前节点的所有子节点进行 DFS 匹配