1268.搜索推荐系统

链接：1268.搜索推荐系统
难度：Medium
标签：字典树、数组、字符串、二分查找、排序、堆（优先队列）
简介：请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

题解 1 - typescript

• 编辑时间：2021-10-25
• 执行用时：820ms
• 内存消耗：66.6MB
• 编程语言：typescript
• 解法介绍：trie 中序遍历。

const MAX_COUNT = 26;
const getIdx = (ch: string) => ch.codePointAt(0)! - 'a'.codePointAt(0)!;
class TrieNode {
  end = false;
  children: TrieNode[] = new Array(MAX_COUNT);
  constructor(public val: string) {}
}
class Trie {
  root = new TrieNode('');
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      const idx = getIdx(ch);
      if (!node.children[idx]) node.children[idx] = new TrieNode(ch);
      node = node.children[idx];
    }
    node.end = true;
  }
  findNode(word: string): TrieNode | null {
    let node = this.root;
    for (const ch of word) {
      const idx = getIdx(ch);
      if (!node.children[idx]) return null;
      node = node.children[idx];
    }
    return node;
  }
  search(word: string): boolean {
    return !!this.findNode(word)?.end;
  }
  startsWith(prefix: string): boolean {
    return !!this.findNode(prefix);
  }
}
function suggestedProducts(products: string[], searchWord: string): string[][] {
  const trie = new Trie();
  products.forEach(ch => trie.insert(ch));
  let str = '';
  const ans: string[][] = [];
  for (const ch of searchWord) {
    const node = trie.findNode(str + ch);
    const list = dfs(node)
      .slice(0, 3)
      .map(v => str + v);
    ans.push(list);
    str += ch;
  }
  return ans;
  function dfs(node: TrieNode | null): string[] {
    const ans: string[] = [];
    _dfs(node);
    return ans;
    function _dfs(node: TrieNode | null, str = ''): void {
      if (!node) return;
      str += node.val;
      if (node.end) ans.push(str);
      for (let i = 0; i < 26; i++) _dfs(node.children[i], str);
    }
  }
}