Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Trie

Guide 5 of 6 · Path 5 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtrie

Replace Words

Problem (restated)

Dictionary of roots. Replace each word in sentence with the shortest root that is a prefix; else keep word.

Intuition

Insert all roots in a trie with end markers. For each word walk until end or miss.

Approaches

Shortest root via trie

Tested only
Time O(Σ L)Space O(Σ L)

Idea. build trie; for word walk chars; on end return path so far.

Walkthrough. dict=[cat,bat,rat], sentence=“the cattle was rattled by the battery” → “the cat was rat by the bat”.

Trade-offs. Sorting roots by length and startsWith also works but trie is linear in total length.

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

export function replaceWords(dictionary: string[], sentence: string): string {
  const root = new Node();
  for (const w of dictionary) {
    let n = root;
    for (const c of w) {
      if (!n.children.has(c)) n.children.set(c, new Node());
      n = n.children.get(c)!;
    }
    n.end = true;
  }
  const replace = (word: string): string => {
    let n = root;
    let path = "";
    for (const c of word) {
      if (!n.children.has(c)) return word;
      n = n.children.get(c)!;
      path += c;
      if (n.end) return path;
    }
    return word;
  };
  return sentence.split(" ").map(replace).join(" ");
}

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

export function replaceWords(dictionary: string[], sentence: string): string {
  const root = new Node();
  for (const w of dictionary) {
    let n = root;
    for (const c of w) {
      if (!n.children.has(c)) n.children.set(c, new Node());
      n = n.children.get(c)!;
    }
    n.end = true;
  }
  const replace = (word: string): string => {
    let n = root;
    let path = "";
    for (const c of word) {
      if (!n.children.has(c)) return word;
      n = n.children.get(c)!;
      path += c;
      if (n.end) return path;
    }
    return word;
  };
  return sentence.split(" ").map(replace).join(" ");
}

Template connection

Trie prefix matching.

Reflection