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

Trie

Guide 2 of 6 · Path 2 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

Design Add and Search Words Data Structure

Problem (restated)

Support addWord(word) and search(word) where search may contain ‘.’ matching any letter.

Intuition

Standard trie insert. On search, ‘.’ branches to every child via DFS.

Approaches

Trie + DFS for '.'

Tested only
Time O(L) add, O(26^L) worst searchSpace O(total chars)

Idea. dfs(i, node): end of word checks End flag; letter follows one child; dot tries all children.

Walkthrough. add “bad”,“dad”,“mad”; search “pad” false, “bad” true, “.ad” true, “b..” true.

Trade-offs. Regex over all words is simpler but slower for many adds.

Solution
type Node = { children: Map<string, Node>; end: boolean };

export class WordDictionary {
  private root: Node = { children: new Map(), end: false };

  addWord(word: string): void {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), end: false });
      n = n.children.get(c)!;
    }
    n.end = true;
  }

  search(word: string): boolean {
    const dfs = (i: number, n: Node): boolean => {
      if (i === word.length) return n.end;
      const c = word[i]!;
      if (c === ".") {
        for (const child of n.children.values()) if (dfs(i + 1, child)) return true;
        return false;
      }
      const next = n.children.get(c);
      return !!next && dfs(i + 1, next);
    };
    return dfs(0, this.root);
  }
}

type Node = { children: Map<string, Node>; end: boolean };

export class WordDictionary {
  private root: Node = { children: new Map(), end: false };

  addWord(word: string): void {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), end: false });
      n = n.children.get(c)!;
    }
    n.end = true;
  }

  search(word: string): boolean {
    const dfs = (i: number, n: Node): boolean => {
      if (i === word.length) return n.end;
      const c = word[i]!;
      if (c === ".") {
        for (const child of n.children.values()) if (dfs(i + 1, child)) return true;
        return false;
      }
      const next = n.children.get(c);
      return !!next && dfs(i + 1, next);
    };
    return dfs(0, this.root);
  }
}

Template connection

Trie with wildcard branching.

Reflection