操作

题一、添加与搜索单词

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

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

方案A、字典树

思路: WordDictionary 类需要支持添加单词和搜索单词的操作，可以使用字典树实现:

对于添加单词，将单词添加到字典树中即可
对于搜索单词，从字典树的根结点开始搜索。由于待搜索的单词可能包含点号，因此在搜索过程中需要考虑点号的处理。对于当前字符是字母和点号的情况，分别按照如下方式处理:
- 如果当前字符是字母，则判断当前字符对应的子结点是否存在，如果子结点存在则移动到子结点，继续搜索下一个字符，如果子结点不存在则说明单词不存在，返回 false
- 如果当前字符是点号，由于点号可以表示任何字母，因此需要对当前结点的所有非空子结点继续搜索下一个字符

重复上述步骤，直到返回 false 或搜索完给定单词的最后一个字符

如果搜索完给定的单词的最后一个字符，则当搜索到的最后一个结点的 isEnd 为 true 时，给定的单词存在。特别地，当搜索到点号时，只要存在一个非空子结点可以搜索到给定的单词，即返回 true

实现

class Trie {
  constructor() {
    this.children = new Array(26).fill(0);
    this.isEnd = false;
  }
  insert(word) {
    let node = this;
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      const index = char.charCodeAt() - "a".charCodeAt();
      if (node.children[index] === 0) {
        node.children[index] = new Trie();
      }
      node = node.children[index];
    }
    node.isEnd = true;
  }
  searchPrefix(prefix) {
    let node = this;
    for (let i = 0; i < prefix.length; i++) {
      const char = prefix[i];
      const index = char.charCodeAt() - "a".charCodeAt();
      if (node.children[index] === 0) {
        return null;
      }
      node = node.children[index];
    }
    return node;
  }
  search(word) {
    const node = this.searchPrefix(word);
    return node != null && node.isEnd;
  }
  startsWith(prefix) {
    return this.startsWith(prefix) != null;
  }
}

class WordDictionary {
  constructor() {
    this.trieRoot = new Trie();
  }
  addWord(word) {
    this.trieRoot.insert(word);
  }
  search(word) {
    const dfs = (index, node) => {
      if (index === word.length) {
        return node.isEnd;
      }
      const ch = word[index];
      if (ch !== ".") {
        const child = node.children[ch.charCodeAt() - "a".charCodeAt()];
        if (child && dfs(index + 1, child)) {
          return true;
        }
      } else {
        for (const child of node.children) {
          if (child && dfs(index + 1, child)) {
            return true;
          }
        }
      }
      return false;
    };
    return dfs(0, this.trieRoot);
  }
}

题一、添加与搜索单词​

方案A、字典树​

题一、添加与搜索单词

方案A、字典树