Overview

  • A trie (prefix tree) is a tree-like data structure that stores strings.
  • It is designed for efficient retrieval of strings, especially when searching by prefixes.

Key Properties

  1. Each node represents a single character of the string.
  2. Strings are stored as paths from the root to leaf nodes.
  3. Common prefixes are shared among strings, making tries memory-efficient for such use cases.

Common Operations

  1. Insert: Add a word to the trie.
  2. Search: Check if a word exists in the trie.
  3. Starts With: Check if any word in the trie starts with a given prefix.

Python Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Example Usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # Output: True
print(trie.search("app"))    # Output: False
print(trie.starts_with("app"))  # Output: True
trie.insert("app")
print(trie.search("app"))    # Output: True

Applications of Tries

  1. Autocomplete

    • Suggest words based on a given prefix.

  2. Spell Checking

    • Quickly verify if a word exists in a dictionary.

  3. Longest Prefix Matching

    • Find the longest prefix of a string that matches a dictionary entry.

  4. Word Search

    • Used in problems like Boggle to efficiently search for words on a board.

  5. IP Routing

    • Store and lookup IP addresses efficiently.

  6. Compressed Storage

    • Tries are used in suffix trees for compressed string storage.

Common Trie Problems

1. Word Search II

Find all words from a given list that can be formed on a board.

def find_words(board, words):
    def backtrack(node, row, col, path):
        if node.is_end_of_word:
            result.add(path)
            node.is_end_of_word = False  # Avoid duplicate results

        if not (0 <= row < len(board) and 0 <= col < len(board[0])):
            return
        char = board[row][col]
        if char not in node.children:
            return

        board[row][col] = "#"  # Mark as visited
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            backtrack(node.children[char], row + dx, col + dy, path + char)
        board[row][col] = char

    # Build trie
    trie = Trie()
    for word in words:
        trie.insert(word)

    result = set()
    for r in range(len(board)):
        for c in range(len(board[0])):
            backtrack(trie.root, r, c, "")

    return list(result)

# Example Usage
board = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
]
words = ["oath", "pea", "eat", "rain"]
print(find_words(board, words))  # Output: ["oath", "eat"]

2. Longest Word in Dictionary

Find the longest word that can be built letter by letter.

def longest_word(words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    words.sort(key=lambda x: (-len(x), x))  # Sort by length and lexicographically

    for word in words:
        node = trie.root
        if all(node.children[char].is_end_of_word for char in word):
            return word
    return ""

# Example Usage
words = ["w", "wo", "wor", "worl", "world"]
print(longest_word(words))  # Output: "world"

Summary

Tries are powerful for prefix-based operations and problems involving dictionaries of words. Their efficient search capabilities make them ideal for applications like autocomplete and word search.