211. 添加与搜索单词 - 数据结构设计

题解

搜索文字，一般会用到 Trie 这种数据结构。而这道题的难点在于处理 word 中存在 . 的情况，因为当处理 . 的时候，需要遍历对应 Trie Node 中的所有字母。

class TrieNode {
  isWord: boolean
  next = new Map<string, TrieNode>()
  constructor(isWord = false) {
    this.isWord = isWord
  }
}
class WordDictionary {
  root: TrieNode
  constructor() {
    this.root = new TrieNode()
  }
  addWord(word: string): void {
    // 1.遍历 word 中的每个字符
    // 2.查看字符是否存在 Trie 中，如果不存在则将字符添加到 Trie 中
    let cur = this.root
    for(const c of word) {
      if (!cur.next.get(c)) {
        cur.next.set(c, new TrieNode())
      }
      cur = cur.next.get(c) as TrieNode
    }
    cur.isWord = true
  }
  search(word: string): boolean {
    // 1.遍历 word 中的每一个字符
    // 2.如果是正常字符，匹配则做递归操作，否则返回 false
    // 3.如果碰到 . 字符，则遍历该节点 next 的所有 key
    return this.match(this.root, word, 0)
  }
  match(node: TrieNode, word: string, index: number): boolean {
    // 当 index === word.length 的时候，表示 word 中的所有字符已经处理完毕，
    // 因此只需要判断节点是否为单词末尾即可。
    if (index === word.length) {
      return node.isWord
    }
    const char = word.charAt(index)
    if (char !== '.') {
      if (!node.next.get(char)) {
        return false
      }
      return this.match(node.next.get(char) as TrieNode, word, index + 1)
    } else {
      // 遍历当前节点的 next 的所有字符
      for (const c of node.next.keys()) {
        if (this.match(node.next.get(c) as TrieNode, word, index + 1)) {
          return true
        }
      }
      return false
    }
  }
}