472.连接词

链接：472.连接词
难度：Hard
标签：深度优先搜索、字典树、数组、字符串、动态规划
简介：给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。

题解 1 - typescript

• 编辑时间：2021-12-28
• 执行用时：4684ms
• 内存消耗：72.9MB
• 编程语言：typescript
• 解法介绍：trie。

class TrieNode {
  end = false;
  children: TrieNode[] = [];
  constructor(public val: string) {}
}
class Trie {
  root = new TrieNode('');
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      const idx = this.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 = this.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);
  }
  getIdx(ch: string) {
    return ch.codePointAt(0)! - 'a'.codePointAt(0)!;
  }
}
function check(trie: Trie, word: string, init = true): boolean {
  if (!init && trie.search(word)) return true;
  for (let i = 0, n = word.length; i < n; i++) {
    if (trie.search(word.substring(0, i)) && check(trie, word.substring(i), false)) return true;
  }
  return false;
}
function findAllConcatenatedWordsInADict(words: string[]): string[] {
  const trie = new Trie();
  return words
    .sort((w1, w2) => w1.length - w2.length)
    .filter(word => {
      if (!word) return false;
      if (check(trie, word)) return true;
      trie.insert(word);
      return false;
    });
}