// ─────────────────────────────────────────────────────────────────────────────
// TRIES (PREFIX TREES)
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : tree keyed by characters; a path from root spells a prefix; shared prefixes share nodes.
// TELL   : "prefix", "autocomplete", "starts with", "dictionary of words", "many lookups against a
//          fixed word set", "wildcard match", "word search II on a grid".
// SAY    : trie / prefix tree, TrieNode, children map, terminal flag (isEnd), insert / search / startsWith,
//          prefix count, DFS collect, pruning (delete leaf nodes after a word is found).
// BIG-O  : insert / search / startsWith O(L) where L = word length; space O(total chars * alphabet).
// NOTE   : children as Map (any alphabet, iteration order), object {} (simple), or Array(26) (fastest, lowercase only).
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. TrieNode / Trie  —  insert, search, startsWith, delete (recursive, prunes empty nodes)  —  O(L) each
class TrieNode {
  children = new Map(); // char -> TrieNode
  isEnd = false;
  count = 0; // number of words passing through (for prefix counts)
}
class Trie {
  root = new TrieNode();
  insert(word) {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, new TrieNode());
      n = n.children.get(c);
      n.count++;
    }
    n.isEnd = true;
  }
  #walk(prefix) { // node at end of prefix, or null
    let n = this.root;
    for (const c of prefix) { n = n.children.get(c); if (!n) return null; }
    return n;
  }
  search(word) { return this.#walk(word)?.isEnd ?? false; }
  startsWith(prefix) { return this.#walk(prefix) !== null; }
  countPrefix(prefix) { return this.#walk(prefix)?.count ?? 0; }
  delete(word) {
    const rec = (n, i) => { // returns true if n should be removed from its parent
      if (i === word.length) { if (!n.isEnd) return false; n.isEnd = false; return n.children.size === 0; }
      const child = n.children.get(word[i]);
      if (!child) return false;
      child.count--;
      if (rec(child, i + 1)) n.children.delete(word[i]);
      return !n.isEnd && n.children.size === 0;
    };
    rec(this.root, 0);
  }
  // ── 2. Autocomplete  —  walk to prefix, DFS collect every isEnd below  —  O(prefix + size of subtree)
  wordsWithPrefix(prefix) {
    const start = this.#walk(prefix), out = [];
    if (!start) return out;
    const dfs = (n, acc) => {
      if (n.isEnd) out.push(acc);
      for (const [c, child] of n.children) dfs(child, acc + c);
    };
    dfs(start, prefix);
    return out;
  }
}
const t = new Trie();
['apple', 'app', 'apt', 'bat'].forEach((w) => t.insert(w));
assert.equal(t.search('app'), true);
assert.equal(t.search('ap'), false);
assert.equal(t.startsWith('ap'), true);
assert.equal(t.search(''), false);
assert.deepEqual(t.wordsWithPrefix('ap'), ['app', 'apple', 'apt']); // pre-order: a word is emitted before its extensions
assert.deepEqual(t.wordsWithPrefix('z'), []);
assert.equal(t.countPrefix('ap'), 3);
t.delete('apple');
assert.equal(t.search('apple'), false);
assert.equal(t.search('app'), true); // prefix word survives
assert.equal(t.countPrefix('ap'), 2);
t.delete('nothere'); // no-op
assert.equal(t.countPrefix('b'), 1);

// ── 3. Word search II idea (trie + grid DFS)  —  build trie of words; DFS grid walking trie nodes; mark cell visited; collect on isEnd
//        PRUNE: set isEnd=false after finding (no dups); optionally delete leaf nodes to shrink the trie. O(mn * 4 * 3^(L-1)) worst.
function findWords(board, words) {
  const trie = new Trie();
  words.forEach((w) => trie.insert(w));
  const m = board.length, n = m ? board[0].length : 0, out = [];
  const dfs = (r, c, node, acc) => {
    if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] === '#') return;
    const ch = board[r][c], next = node.children.get(ch);
    if (!next) return;
    if (next.isEnd) { out.push(acc + ch); next.isEnd = false; }
    board[r][c] = '#'; // visited
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) dfs(r + dr, c + dc, next, acc + ch);
    board[r][c] = ch; // un-choose
  };
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) dfs(r, c, trie.root, '');
  return out.sort();
}
assert.deepEqual(findWords([['o', 'a', 'a', 'n'], ['e', 't', 'a', 'e'], ['i', 'h', 'k', 'r'], ['i', 'f', 'l', 'v']], ['oath', 'pea', 'eat', 'rain']), ['eat', 'oath']);
assert.deepEqual(findWords([['a']], ['a', 'b']), ['a']);
assert.deepEqual(findWords([], ['a']), []);

// ── 4. Longest common prefix via trie  —  walk down while exactly one child and not isEnd  —  O(total chars)
function longestCommonPrefix(words) {
  if (words.length === 0) return '';
  const trie = new Trie();
  words.forEach((w) => trie.insert(w));
  let n = trie.root, out = '';
  while (n.children.size === 1 && !n.isEnd) {
    const [c, child] = n.children.entries().next().value;
    out += c; n = child;
  }
  return out;
}
assert.equal(longestCommonPrefix(['flower', 'flow', 'flight']), 'fl');
assert.equal(longestCommonPrefix(['dog', 'racecar']), '');
assert.equal(longestCommonPrefix(['a']), 'a');

// ── 5. Replace words (shortest root in dictionary)  —  walk each word; stop at first isEnd  —  O(total chars)
function replaceWords(dict, sentence) {
  const trie = new Trie();
  dict.forEach((w) => trie.insert(w));
  const shortestRoot = (w) => {
    let n = trie.root, acc = '';
    for (const c of w) {
      n = n.children.get(c);
      if (!n) return w;
      acc += c;
      if (n.isEnd) return acc;
    }
    return w;
  };
  return sentence.split(' ').map(shortestRoot).join(' ');
}
assert.equal(replaceWords(['cat', 'bat', 'rat'], 'the cattle was rattled by the battery'), 'the cat was rat by the bat');
assert.equal(replaceWords(['a', 'aa'], 'aaa aab'), 'a a');
assert.equal(replaceWords([], 'x y'), 'x y');

// ── 6. Add and search word with '.' wildcard  —  DFS; on '.', try every child  —  O(26^dots * L) worst
class WordDictionary {
  #root = new TrieNode();
  addWord(w) {
    let n = this.#root;
    for (const c of w) { if (!n.children.has(c)) n.children.set(c, new TrieNode()); n = n.children.get(c); }
    n.isEnd = true;
  }
  search(w) {
    const dfs = (n, i) => {
      if (i === w.length) return n.isEnd;
      if (w[i] === '.') { for (const child of n.children.values()) if (dfs(child, i + 1)) return true; return false; }
      const child = n.children.get(w[i]);
      return child ? dfs(child, i + 1) : false;
    };
    return dfs(this.#root, 0);
  }
}
const wd = new WordDictionary();
['bad', 'dad', 'mad'].forEach((w) => wd.addWord(w));
assert.equal(wd.search('pad'), false);
assert.equal(wd.search('.ad'), true);
assert.equal(wd.search('b..'), true);
assert.equal(wd.search('b...'), false);

// ── 7. Count words with given prefix  —  per-node counter incremented on insert (see Trie.countPrefix)  —  O(L)
const t2 = new Trie();
['pay', 'attention', 'practice', 'attend'].forEach((w) => t2.insert(w));
assert.equal(t2.countPrefix('at'), 2);
assert.equal(t2.countPrefix('p'), 2);
assert.equal(t2.countPrefix('zz'), 0);

// ── 8. Children representation note (say it when asked about space)
//   Map            : any alphabet (unicode), predictable iteration, ~most memory per node.
//   object {}      : simplest to write; fine for lowercase; watch out for inherited keys (use Object.create(null) or Map).
//   Array(26)      : children[c.charCodeAt(0) - 97]; fastest and most compact for lowercase a-z; wastes 26 slots per node.
class ArrayTrieNode { children = new Array(26).fill(null); isEnd = false; }
const atn = new ArrayTrieNode();
atn.children['c'.charCodeAt(0) - 97] = new ArrayTrieNode();
assert.ok(atn.children[2] instanceof ArrayTrieNode);
assert.equal(atn.children[0], null);

console.log('ok: algorithms/tries.js');