648. Replace Words☆

interface TrieNode {
  children: Map<string, TrieNode>;
  word: string | null;   // non-null only at the end of a word
}

function findWords(board: string[][], words: string[]): string[] {
  // 1. Build a trie of all target words.
  const root: TrieNode = { children: new Map(), word: null };
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node.children.has(ch)) {
        node.children.set(ch, { children: new Map(), word: null });
      }
      node = node.children.get(ch)!;
    }
    node.word = w;             // mark terminal
  }

  const rows = board.length;
  const cols = board[0].length;
  const found: string[] = [];

  function dfs(r: number, c: number, node: TrieNode): void {
    const ch = board[r][c];
    const next = node.children.get(ch);
    if (!next) return;         // prune: no word continues here

    if (next.word !== null) {  // reached a complete word
      found.push(next.word);
      next.word = null;        // de-dupe without a Set
    }

    board[r][c] = '#';         // mark visited
    for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
        dfs(nr, nc, next);
      }
    }
    board[r][c] = ch;          // restore (backtrack)
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      dfs(r, c, root);         // start only matters if board[r][c] is a root edge
    }
  }
  return found;
}

class TrieNode {
  children: Record<string, TrieNode> = {};
  // Up to 3 lexicographically smallest products passing through this node.
  suggestions: string[] = [];
}

function suggestedProducts(products: string[], searchWord: string): string[][] {
  products.sort();                       // global lexicographic order

  const root = new TrieNode();
  for (const product of products) {      // insert each product...
    let node = root;
    for (const c of product) {
      if (!node.children[c]) node.children[c] = new TrieNode();
      node = node.children[c];
      if (node.suggestions.length < 3)   // ...caching it on every prefix node
        node.suggestions.push(product);  // products are inserted in sorted
    }                                    // order, so the first 3 are the answer
  }

  const result: string[][] = [];
  let node: TrieNode | null = root;
  for (const c of searchWord) {          // type one character at a time
    node = node ? node.children[c] ?? null : null;
    result.push(node ? node.suggestions : []);
  }
  return result;
}

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  end = false;
}

class WordDictionary {
  private root = new TrieNode();

  addWord(word: string): void {
    let node = this.root;
    for (const ch of word) {                 // walk, creating edges
      let next = node.children.get(ch);
      if (!next) {
        next = new TrieNode();
        node.children.set(ch, next);
      }
      node = next;
    }
    node.end = true;                          // mark a complete word
  }

  search(word: string): boolean {
    const dfs = (node: TrieNode, i: number): boolean => {
      if (i === word.length) return node.end; // consumed pattern → is it a word?
      const ch = word[i];
      if (ch === '.') {                        // wildcard: try EVERY child
        for (const child of node.children.values()) {
          if (dfs(child, i + 1)) return true;
        }
        return false;                          // no branch worked
      }
      const next = node.children.get(ch);      // literal: one edge only
      return next ? dfs(next, i + 1) : false;
    };
    return dfs(this.root, 0);
  }
}

class TrieNode {
  children: Record<string, TrieNode> = {};
  isEnd = false;
}

function replaceWords(dictionary: string[], sentence: string): string {
  // 1) Build a trie of the dictionary roots.
  const root = new TrieNode();
  for (const w of dictionary) {
    let node = root;
    for (const c of w) {
      if (!node.children[c]) node.children[c] = new TrieNode();
      node = node.children[c];
    }
    node.isEnd = true;                 // mark end-of-root
  }

  // 2) For each word, walk the trie until the first end-of-root.
  const shortestRoot = (word: string): string => {
    let node = root;
    let prefix = '';
    for (const c of word) {
      if (!node.children[c]) break;    // fell off the trie → no root
      prefix += c;
      node = node.children[c];
      if (node.isEnd) return prefix;   // first root wins (shortest)
    }
    return word;                       // no root matched → keep original
  };

  return sentence.split(' ').map(shortestRoot).join(' ');
}