[AlgoMastery]
Topics›String›Trie for Strings
📖

Trie for Strings

String
~20 min read
5 practice problems

Overview

Trie (Prefix Tree) is a tree-like data structure optimized for storing and searching strings. Each node represents a character, and paths from root to nodes form strings. Tries excel at prefix matching, autocomplete, and efficient string lookups.

Key advantages:

  • Fast prefix search: O(m) where m is pattern length
  • Space-efficient for shared prefixes
  • Supports insertion, deletion, and search
  • Ideal for dictionary/autocomplete problems

Common Trie problems include:

  • Word search and prefix matching
  • Autocomplete suggestions
  • Word break problems
  • Longest common prefix
  • Replace words
  • Maximum XOR queries

Pattern 1: Basic Trie Structure

Implement a basic Trie with insert, search, and startsWith operations.

class TrieNode {
  children: Map<string, TrieNode>;
  isEnd: boolean;
  
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  root: TrieNode;
  
  constructor() {
    this.root = new TrieNode();
  }
  
  insert(word: string): void {
    let node = this.root;
    
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    
    node.isEnd = true;
  }
  
  search(word: string): boolean {
    let node = this.root;
    
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    
    return node.isEnd;
  }
  
  startsWith(prefix: string): boolean {
    let node = this.root;
    
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    
    return true;
  }
}

Time: Insert/Search/StartsWith O(m), Space: O(ALPHABET_SIZE N M) where N is number of words, M is average length

Array-based implementation (for lowercase letters):

class TrieNodeArray {
  children: (TrieNodeArray | null)[];
  isEnd: boolean;
  
  constructor() {
    this.children = Array(26).fill(null);
    this.isEnd = false;
  }
}

class TrieArray {
  root: TrieNodeArray;
  
  constructor() {
    this.root = new TrieNodeArray();
  }
  
  private charToIndex(char: string): number {
    return char.charCodeAt(0) - 'a'.charCodeAt(0);
  }
  
  insert(word: string): void {
    let node = this.root;
    
    for (const char of word) {
      const index = this.charToIndex(char);
      if (!node.children[index]) {
        node.children[index] = new TrieNodeArray();
      }
      node = node.children[index]!;
    }
    
    node.isEnd = true;
  }
  
  search(word: string): boolean {
    let node = this.root;
    
    for (const char of word) {
      const index = this.charToIndex(char);
      if (!node.children[index]) {
        return false;
      }
      node = node.children[index]!;
    }
    
    return node.isEnd;
  }
  
  startsWith(prefix: string): boolean {
    let node = this.root;
    
    for (const char of prefix) {
      const index = this.charToIndex(char);
      if (!node.children[index]) {
        return false;
      }
      node = node.children[index]!;
    }
    
    return true;
  }
}

Pattern 2: Delete Operation

Remove a word from Trie.

class TrieWithDelete extends Trie {
  delete(word: string): boolean {
    return this._delete(this.root, word, 0);
  }
  
  private _delete(node: TrieNode, word: string, index: number): boolean {
    if (index === word.length) {
      if (!node.isEnd) return false;
      node.isEnd = false;
      return node.children.size === 0;
    }
    
    const char = word[index];
    const child = node.children.get(char);
    
    if (!child) return false;
    
    const shouldDeleteChild = this._delete(child, word, index + 1);
    
    if (shouldDeleteChild) {
      node.children.delete(char);
      return node.children.size === 0 && !node.isEnd;
    }
    
    return false;
  }
}

Time: O(m), Space: O(1) additional

Pattern 3: Find All Words with Prefix

Retrieve all words that start with a given prefix.

class TrieWithPrefixSearch extends Trie {
  findAllWithPrefix(prefix: string): string[] {
    let node = this.root;
    
    // Navigate to prefix node
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return [];
      }
      node = node.children.get(char)!;
    }
    
    // Collect all words from this node
    const results: string[] = [];
    this._collectWords(node, prefix, results);
    return results;
  }
  
  private _collectWords(node: TrieNode, prefix: string, results: string[]): void {
    if (node.isEnd) {
      results.push(prefix);
    }
    
    for (const [char, child] of node.children) {
      this._collectWords(child, prefix + char, results);
    }
  }
}

Time: O(m + k) where k is number of words with prefix, Space: O(k)

Pattern 4: Longest Common Prefix

Find the longest common prefix among strings using Trie.

function longestCommonPrefix(words: string[]): string {
  if (words.length === 0) return '';
  
  const trie = new Trie();
  for (const word of words) {
    trie.insert(word);
  }
  
  let node = trie.root;
  let prefix = '';
  
  while (node.children.size === 1 && !node.isEnd) {
    const [char, child] = Array.from(node.children)[0];
    prefix += char;
    node = child;
  }
  
  return prefix;
}

Time: O(S) where S is sum of all characters, Space: O(S)

Alternative without Trie:

function longestCommonPrefixSimple(words: string[]): string {
  if (words.length === 0) return '';
  
  let prefix = words[0];
  
  for (let i = 1; i < words.length; i++) {
    while (!words[i].startsWith(prefix)) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix === '') return '';
    }
  }
  
  return prefix;
}

Pattern 5: Word Search II (Multiple Patterns)

Find all words from dictionary that exist in a 2D board.

function findWords(board: string[][], words: string[]): string[] {
  const trie = new Trie();
  for (const word of words) {
    trie.insert(word);
  }
  
  const results = new Set<string>();
  const rows = board.length;
  const cols = board[0].length;
  
  const dfs = (node: TrieNode, i: number, j: number, path: string): void => {
    if (node.isEnd) {
      results.add(path);
    }
    
    if (i < 0 || i >= rows || j < 0 || j >= cols) return;
    
    const char = board[i][j];
    const child = node.children.get(char);
    
    if (!child) return;
    
    // Mark as visited
    board[i][j] = '#';
    
    // Explore neighbors
    dfs(child, i + 1, j, path + char);
    dfs(child, i - 1, j, path + char);
    dfs(child, i, j + 1, path + char);
    dfs(child, i, j - 1, path + char);
    
    // Restore
    board[i][j] = char;
  };
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      dfs(trie.root, i, j, '');
    }
  }
  
  return Array.from(results);
}

Time: O(M N 4^L) where L is max word length, Space: O(ALPHABET_SIZE N M)

Pattern 6: Replace Words

Replace words in sentence with shortest root from dictionary.

function replaceWords(dictionary: string[], sentence: string): string {
  const trie = new Trie();
  for (const word of dictionary) {
    trie.insert(word);
  }
  
  const words = sentence.split(' ');
  const result: string[] = [];
  
  for (const word of words) {
    let node = trie.root;
    let prefix = '';
    let found = false;
    
    for (const char of word) {
      if (!node.children.has(char)) break;
      
      prefix += char;
      node = node.children.get(char)!;
      
      if (node.isEnd) {
        result.push(prefix);
        found = true;
        break;
      }
    }
    
    if (!found) {
      result.push(word);
    }
  }
  
  return result.join(' ');
}

Time: O(N M) where N is sentence length, M is average word length, Space: O(ALPHABET_SIZE D * M)

Pattern 7: Word Break

Check if string can be segmented into dictionary words using Trie.

function wordBreak(s: string, wordDict: string[]): boolean {
  const trie = new Trie();
  for (const word of wordDict) {
    trie.insert(word);
  }
  
  const memo = new Map<number, boolean>();
  
  const dfs = (start: number): boolean => {
    if (start === s.length) return true;
    if (memo.has(start)) return memo.get(start)!;
    
    let node = trie.root;
    
    for (let i = start; i < s.length; i++) {
      const char = s[i];
      if (!node.children.has(char)) break;
      
      node = node.children.get(char)!;
      
      if (node.isEnd && dfs(i + 1)) {
        memo.set(start, true);
        return true;
      }
    }
    
    memo.set(start, false);
    return false;
  };
  
  return dfs(0);
}

Time: O(n^2 + m k) where n is string length, m is dict size, k is avg word length, Space: O(n + ALPHABET_SIZE m * k)

Pattern 8: Autocomplete Suggestions

Implement autocomplete with Trie.

class AutocompleteSystem {
  trie: TrieWithPrefixSearch;
  currentQuery: string;
  
  constructor(sentences: string[], times: number[]) {
    this.trie = new TrieWithPrefixSearch();
    this.currentQuery = '';
    
    // Store sentences with frequency
    for (let i = 0; i < sentences.length; i++) {
      this.trie.insert(sentences[i]);
      // In real implementation, store frequency in TrieNode
    }
  }
  
  input(c: string): string[] {
    if (c === '#') {
      this.trie.insert(this.currentQuery);
      this.currentQuery = '';
      return [];
    }
    
    this.currentQuery += c;
    const suggestions = this.trie.findAllWithPrefix(this.currentQuery);
    
    // Sort by frequency (simplified - return top 3)
    return suggestions.slice(0, 3);
  }
}

Enhanced with frequency:

class TrieNodeWithFreq extends TrieNode {
  frequency: number;
  
  constructor() {
    super();
    this.frequency = 0;
  }
}

class AutocompleteTrie {
  root: TrieNodeWithFreq;
  
  constructor() {
    this.root = new TrieNodeWithFreq();
  }
  
  insert(word: string, freq: number = 1): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNodeWithFreq());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
    (node as TrieNodeWithFreq).frequency += freq;
  }
  
  getTopSuggestions(prefix: string, topK: number): Array<{word: string, freq: number}> {
    let node = this.root;
    
    for (const char of prefix) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    
    const results: Array<{word: string, freq: number}> = [];
    this._collectWithFreq(node, prefix, results);
    
    results.sort((a, b) => {
      if (b.freq !== a.freq) return b.freq - a.freq;
      return a.word.localeCompare(b.word);
    });
    
    return results.slice(0, topK);
  }
  
  private _collectWithFreq(node: TrieNode, prefix: string, results: Array<{word: string, freq: number}>): void {
    if (node.isEnd) {
      results.push({word: prefix, freq: (node as TrieNodeWithFreq).frequency});
    }
    
    for (const [char, child] of node.children) {
      this._collectWithFreq(child, prefix + char, results);
    }
  }
}

Pattern 9: Maximum XOR

Find maximum XOR of a number with any number in array using Trie.

class BinaryTrieNode {
  children: (BinaryTrieNode | null)[];
  
  constructor() {
    this.children = [null, null];
  }
}

class BinaryTrie {
  root: BinaryTrieNode;
  
  constructor() {
    this.root = new BinaryTrieNode();
  }
  
  insert(num: number): void {
    let node = this.root;
    
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1;
      if (!node.children[bit]) {
        node.children[bit] = new BinaryTrieNode();
      }
      node = node.children[bit]!;
    }
  }
  
  findMaxXOR(num: number): number {
    let node = this.root;
    let result = 0;
    
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1;
      const desiredBit = 1 - bit;
      
      if (node.children[desiredBit]) {
        result |= (1 << i);
        node = node.children[desiredBit]!;
      } else {
        node = node.children[bit]!;
      }
    }
    
    return result;
  }
}

function findMaximumXOR(nums: number[]): number {
  const trie = new BinaryTrie();
  let maxXOR = 0;
  
  for (const num of nums) {
    trie.insert(num);
    maxXOR = Math.max(maxXOR, trie.findMaxXOR(num));
  }
  
  return maxXOR;
}

Time: O(n 32), Space: O(n 32)

Pattern 10: Concatenated Words

Find all words that can be formed by concatenating other words.

function findAllConcatenatedWordsInADict(words: string[]): string[] {
  const trie = new Trie();
  for (const word of words) {
    trie.insert(word);
  }
  
  const results: string[] = [];
  
  for (const word of words) {
    if (canForm(word, trie, 0, 0)) {
      results.push(word);
    }
  }
  
  return results;
}

function canForm(word: string, trie: Trie, start: number, count: number): boolean {
  if (start === word.length) {
    return count >= 2;
  }
  
  let node = trie.root;
  
  for (let i = start; i < word.length; i++) {
    const char = word[i];
    if (!node.children.has(char)) return false;
    
    node = node.children.get(char)!;
    
    if (node.isEnd && canForm(word, trie, i + 1, count + 1)) {
      return true;
    }
  }
  
  return false;
}

Time: O(n m^2) where n is words count, m is avg length, Space: O(ALPHABET_SIZE n * m)

Pattern 11: Prefix and Suffix Search

Design system to search words by both prefix and suffix.

class WordFilter {
  trie: TrieNode;
  
  constructor(words: string[]) {
    this.trie = new TrieNode();
    
    for (let weight = 0; weight < words.length; weight++) {
      const word = words[weight];
      const suffixWord = '#' + word;
      
      // Insert all suffixes
      for (let i = word.length - 1; i >= 0; i--) {
        const node = new TrieNode();
        node.weight = weight;
        
        let current = this.trie;
        for (const char of word.substring(i) + suffixWord) {
          if (!current.children.has(char)) {
            current.children.set(char, new TrieNode());
          }
          current = current.children.get(char)!;
          current.weight = weight;
        }
      }
    }
  }
  
  f(prefix: string, suffix: string): number {
    let node = this.trie;
    const searchKey = suffix + '#' + prefix;
    
    for (const char of searchKey) {
      if (!node.children.has(char)) {
        return -1;
      }
      node = node.children.get(char)!;
    }
    
    return node.weight;
  }
}

Time: O(N K^2) construction, O(P + S) query, Space: O(N K^2)

Pattern 12: Stream of Characters

Check if suffix of stream forms any word in dictionary.

class StreamChecker {
  trie: TrieNode;
  stream: string;
  maxLength: number;
  
  constructor(words: string[]) {
    this.trie = new TrieNode();
    this.stream = '';
    this.maxLength = 0;
    
    // Insert reversed words
    for (const word of words) {
      this.maxLength = Math.max(this.maxLength, word.length);
      let node = this.trie;
      
      for (let i = word.length - 1; i >= 0; i--) {
        const char = word[i];
        if (!node.children.has(char)) {
          node.children.set(char, new TrieNode());
        }
        node = node.children.get(char)!;
      }
      
      node.isEnd = true;
    }
  }
  
  query(letter: string): boolean {
    this.stream = (letter + this.stream).substring(0, this.maxLength);
    
    let node = this.trie;
    for (const char of this.stream) {
      if (!node.children.has(char)) return false;
      node = node.children.get(char)!;
      if (node.isEnd) return true;
    }
    
    return false;
  }
}

Time: O(m) per query where m is max word length, Space: O(ALPHABET_SIZE N M)

When to Use Trie

Use Trie when:

  • Problem involves prefix matching or autocomplete
  • Need to search multiple patterns efficiently
  • Dictionary lookups with shared prefixes
  • Word break or concatenation problems
  • Longest common prefix among strings
  • Stream processing with pattern matching

Template (Basic Trie)

class TrieTemplate {
  root: TrieNode;
  
  constructor() {
    this.root = new TrieNode();
  }
  
  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }
  
  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) return false;
      node = node.children.get(char)!;
    }
    return node.isEnd;
  }
}

Template (DFS on Trie)

function dfsOnTrie(node: TrieNode, path: string, callback: (word: string) => void): void {
  if (node.isEnd) {
    callback(path);
  }
  
  for (const [char, child] of node.children) {
    dfsOnTrie(child, path + char, callback);
  }
}

Time and Space Complexity Summary

  • Insert: O(m) time, O(m) space
  • Search: O(m) time, O(1) space
  • Prefix search: O(m) time, O(1) space
  • Delete: O(m) time, O(1) space
  • Find all with prefix: O(m + k) time, O(k) space
  • Word search II: O(M N 4^L) time
  • Space: O(ALPHABET_SIZE N M) where N is number of words, M is average length

Practice Tips

  1. Choose implementation — Map for flexibility, Array for fixed alphabet
  2. Handle edge cases — Empty strings, null nodes
  3. Optimize space — Consider compressed Trie for sparse data
  4. Use memoization — For repeated queries
  5. Consider alternatives — Hash set for exact matches, Trie for prefixes
  6. Clean up nodes — When deleting, remove unused nodes

Common Mistakes

  1. Not checking isEnd — Distinguish between prefix and complete word
  2. Memory leaks — Not cleaning up deleted nodes
  3. Wrong traversal — Confusing DFS vs BFS
  4. Index errors — Array-based implementation index calculation
  5. Case sensitivity — Handle case consistently

Related Concepts

  • Tree Data Structures — Understanding tree traversal
  • Hash Tables — Alternative for exact matches
  • String Matching — KMP, Rabin-Karp algorithms
  • Dynamic Programming — For word break optimization

Trie is a powerful data structure for string problems. Master these patterns, and you'll be well-prepared for prefix matching and dictionary-related interview questions.

← PreviousString ValidationNext →Suffix Arrays