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

链接：211.添加与搜索单词-数据结构设计
难度：Medium
标签：深度优先搜索、设计、字典树、字符串
简介：请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

题解 1 - typescript

• 编辑时间：2021-10-19
• 执行用时：216ms
• 内存消耗：56.6MB
• 编程语言：typescript
• 解法介绍：trie。

class TrieNode {
  end = false;
  children: Map<string, TrieNode> = new Map();
  constructor(public val: string) {}
}
class Trie {
  private _size = 0;
  get size() {
    return this._size;
  }
  get empty() {
    return this._size === 0;
  }
  private _root = new TrieNode('');
  get root() {
    return this._root;
  }
  clear() {
    this._root = new TrieNode('');
    this._size = 0;
  }
  add(str: string) {
    return this._add(str);
  }
  private _add(str: string, node = this._root) {
    if (str.length === 0) {
      this._root.end = true;
      this._size++;
      return;
    }
    if (str.length === 1) {
      let endNode = node.children.get(str);
      if (!endNode) node.children.set(str, (endNode = new TrieNode(str)));
      if (!endNode.end) {
        endNode.end = true;
        this._size++;
      }
      return;
    }
    const first = str[0];
    let nextNode = node.children.get(first);
    if (!nextNode) node.children.set(first, (nextNode = new TrieNode(first)));
    const nextStr = str.substr(1);
    this._add(nextStr, nextNode);
  }
  contains(str: string) {
    const endNode = this.findEndNode(str);
    return endNode ? endNode.end : false;
  }
  remove(str: string) {
    const endNode = this.findEndNode(str);
    if (endNode && endNode.end) {
      endNode.end = false;
      this._size--;
    }
  }
  starsWith(str: string) {
    return this.findEndNode(str) !== null;
  }
  private findEndNode(str: string, node = this._root): TrieNode | null {
    if (str.length === 0) return this._root;
    if (str.length === 1) return node.children.get(str) ?? null;
    const first = str[0];
    let nextNode = node.children.get(first);
    if (!nextNode) return null;
    const nextStr = str.substr(1);
    return this.findEndNode(nextStr, nextNode);
  }
}
class WordDictionary {
  private trie = new Trie();
  addWord(word: string): void {
    this.trie.add(word);
  }
  search(word: string): boolean {
    return this._search(0, word, this.trie.root);
  }
  private _search(idx: number, word: string, node: TrieNode): boolean {
    const ch = word[idx];
    if (idx === word.length - 1) {
      if (ch === '.') return Array.from(node.children.values()).some(node => node.end);
      const lastNode = node.children.get(ch);
      return !!lastNode?.end;
    }
    if (ch === '.') {
      for (const nextNode of node.children.values()) {
        if (this._search(idx + 1, word, nextNode)) return true;
      }
      return false;
    }
    const nextNode = node.children.get(ch);
    if (!nextNode) return false;
    return this._search(idx + 1, word, nextNode);
  }
}