Tries (Prefix Trees)

// A trie node: one child per next character, plus a flag that says "a word ends here".
class TrieNode {
  constructor() {
    this.children = new Map(); // character -> TrieNode
    this.isEnd = false;
  }
}

export class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true; // the path alone doesn't make a word: mark where this one ends
  }

  // The node reached by following prefix from the root, or null if the path breaks off.
  find(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }

  search(word) {
    const node = this.find(word);
    return node !== null && node.isEnd; // the path must exist AND end a word
  }

  startsWith(prefix) {
    return this.find(prefix) !== null;  // any path at all is enough
  }

  // Autocomplete: every stored word that starts with prefix, found by a DFS below the prefix's node.
  wordsWithPrefix(prefix) {
    const out = [];
    const dfs = (node, path) => {
      if (node.isEnd) out.push(path);
      for (const [ch, child] of node.children) dfs(child, path + ch);
    };
    const start = this.find(prefix);
    if (start) dfs(start, prefix);
    return out;
  }
}

// The same trie with a fixed array of 26 children per node, for lowercase 'a' to 'z' only.
// No hashing, so it is fast and predictable; but every node pays for 26 slots even if it uses one.
const CODE_A = 'a'.charCodeAt(0);
const arrayNode = () => ({ next: new Array(26).fill(null), isEnd: false });

export class ArrayTrie {
  constructor() {
    this.root = arrayNode();
  }

  insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      const c = word.charCodeAt(i) - CODE_A; // 'a' -> 0, 'b' -> 1, … 'z' -> 25
      node.next[c] ??= arrayNode();
      node = node.next[c];
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root;
    for (let i = 0; i < word.length && node !== null; i++) node = node.next[word.charCodeAt(i) - CODE_A];
    return node !== null && node.isEnd;
  }
}

// Wildcard search on a trie (built with the Trie template): '.' matches any one character.
// A letter follows a single edge; a dot branches into every child. A branch that breaks off dies at once.
export function matchesPattern(trie, pattern) {
  const dfs = (node, i) => {
    if (i === pattern.length) return node.isEnd;   // used up the pattern: is this a whole word?
    const ch = pattern[i];
    if (ch !== '.') {
      const child = node.children.get(ch);
      return child !== undefined && dfs(child, i + 1);
    }
    for (const child of node.children.values()) {
      if (dfs(child, i + 1)) return true;          // stop at the first branch that matches
    }
    return false;
  };
  return dfs(trie.root, 0);
}

// Pruned search: from each start position, walk the trie while reading the text, and stop the moment no stored
// word continues that way. Finds every dictionary word that appears in text, as [start, word] pairs.
export function findAllMatches(text, trie) {
  const found = [];
  for (let start = 0; start < text.length; start++) {
    let node = trie.root;
    for (let end = start; end < text.length; end++) {
      node = node.children.get(text[end]);
      if (!node) break;                                   // dead end: no word has this prefix, so stop early
      if (node.isEnd) found.push([start, text.slice(start, end + 1)]);
    }
  }
  return found;
}