19. Tries

Theory

A trie (prefix tree) stores strings character-by-character. Shared prefixes are stored once, which makes prefix search and autocomplete efficient.

See the full write-up: Data Structures - Trie.

When FAANG asks: autocomplete, prefix search, word dictionary with wildcards (LC 211), or grid + DFS with a trie (LC 212 Word Search II). Prefer a hash set of prefixes when you only need exact words; use a trie when you need prefix completion or shared-prefix compression.

Use trie	Use hash set / dict instead
Prefix matching (startsWith)	Exact word lookup only
Autocomplete / top-k suggestions	One-off membership checks
Word Search II (prune dead paths early)	Small, fixed word list on a grid
Wildcard search with . (LC 211)	No prefix or wildcard queries
Binary trie for max XOR (LC 421)	—

Problems at a glance

LC	Problem
208	Implement Trie (Prefix Tree)	↗
720	Longest Word in Dictionary	↗
677	Map Sum Pairs	↗
212	Word Search II	↗
648	Replace Words	↗
211	Add and Search Word	↗
421	Maximum XOR of Two Numbers in an Array	↗
1268	Search Suggestions System	↗
2255	Count Prefixes of a Given String	↗

---

Problems

Problem 1: Implement Trie (Prefix Tree) (Leetcode:208)

Problem Statement

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Code and Explanation

Approach 1 — Hash Map ChildrenApproach 2 — Fixed Array Children

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Explanation:
Each node stores a map of child characters. Walk the trie for every operation:

1. Insert — follow/create edges for each character; mark the last node as a word end.
2. Search — follow edges; return true only if the path exists and is_end is set.
3. startsWith — same walk, but any existing prefix path is enough (no is_end check).

A shared helper _find keeps search and prefix logic DRY.

Time: O(L) per operation · Space: O(total characters stored)

class TrieNode:
    def __init__(self):
        self.children: list[TrieNode | None] = [None] * 26
        self.is_end = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            idx = ord(char) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = TrieNode()
            node = node.children[idx]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            idx = ord(char) - ord("a")
            if node.children[idx] is None:
                return None
            node = node.children[idx]
        return node

Explanation:
When the alphabet is fixed (26 lowercase letters), an array of size 26 per node avoids hash-map overhead and gives O(1) child lookup via index. Same logic as Approach 1 — trade a bit more memory for faster constant factors.

Time: O(L) per operation · Space: O(26 · nodes) worst case

Problem 2: Longest Word in Dictionary (Leetcode:720)

Problem Statement

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Note that the word should be built from left to right with each additional character being added to the end of a previous word.

Example 1:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 30
• words[i] consists of lowercase English letters.

Code and Explanation

Approach 1 — Trie + DFSApproach 2 — Sort + Hash Set

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False

class Solution:
    def longestWord(self, words: list[str]) -> str:
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_end = True

        best = ""

        def dfs(node: TrieNode, path: str) -> None:
            nonlocal best
            if len(path) > len(best) or (len(path) == len(best) and path < best):
                best = path
            for char in sorted(node.children):
                child = node.children[char]
                if child.is_end:
                    dfs(child, path + char)

        dfs(root, "")
        return best

Explanation:
Build a trie of all words. A word is "buildable" iff every prefix along its path is also marked is_end. DFS from the root, visiting children in sorted order (for lex tie-breaking), only continuing through nodes that end a valid prefix.

1. Insert every word into the trie.
2. DFS from root with empty path.
3. At each is_end node, update the best candidate and recurse to children.

Time: O(N · L + N log N) · Space: O(N · L)

class Solution:
    def longestWord(self, words: list[str]) -> str:
        word_set = set(words)
        words.sort(key=lambda w: (-len(w), w))

        for word in words:
            if all(word[:i] in word_set for i in range(1, len(word))):
                return word
        return ""

Explanation:
Sort words by descending length, then lex order. The first word whose every proper prefix exists in a hash set is the answer. No trie needed — prefix checks are O(L) hash lookups — but sorting upfront handles the tie-breaking.

Time: O(N · L log N) · Space: O(N · L)

Problem 3: Map Sum Pairs (Leetcode:677)

Problem Statement

Design a map that allows you to do the following:

• Maps a string key to a given value.
• Returns the sum of the values that have a key with a prefix equal to a given string.

Implement the MapSum class:

• MapSum() Initializes the MapSum object.
• void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
• int sum(string prefix) Returns the sum of all the pairs' value whose key starts with the prefix.

Example 1:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)

Constraints:

• 1 <= key.length, prefix.length <= 50
• key and prefix consist of only lowercase English letters.
• 1 <= val <= 1000
• At most 50 calls will be made to insert and sum.

Code and Explanation

Approach 1 — Trie with Running SumApproach 2 — Hash Map Scan

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.sum = 0

class MapSum:
    def __init__(self):
        self.root = TrieNode()
        self.values: dict[str, int] = {}

    def insert(self, key: str, val: int) -> None:
        delta = val - self.values.get(key, 0)
        self.values[key] = val

        node = self.root
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.sum += delta

    def sum(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.sum

Explanation:
Store a running sum at every trie node. When inserting, compute the delta from the old value (0 if new key) and add it along the key's path. sum(prefix) is then a single O(L) walk to the prefix node.

1. Track previous values in a hash map for override handling.
2. On insert, propagate delta down the trie path.
3. On sum, return node.sum at the prefix endpoint.

Time: O(L) per insert/sum · Space: O(total key characters)

class MapSum:
    def __init__(self):
        self.values: dict[str, int] = {}

    def insert(self, key: str, val: int) -> None:
        self.values[key] = val

    def sum(self, prefix: str) -> int:
        return sum(
            v for k, v in self.values.items()
            if k.startswith(prefix)
        )

Explanation:
Store key→value in a hash map and scan all keys on each sum call. Simple and fine for tiny inputs (≤ 50 calls here), but O(K · L) per query vs O(L) with a trie.

Time: O(K · L) per sum · Space: O(K)

Problem 4: Word Search II (Leetcode:212)

Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Code and Explanation

Approach 1 — Trie + BacktrackingApproach 2 — Hash Set + Backtracking

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.word: str | None = None

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        rows, cols = len(board), len(board[0])
        result: list[str] = []

        def dfs(r: int, c: int, node: TrieNode) -> None:
            char = board[r][c]
            if char not in node.children:
                return

            next_node = node.children[char]
            if next_node.word:
                result.append(next_node.word)
                next_node.word = None  # avoid duplicates

            board[r][c] = "#"
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                    dfs(nr, nc, next_node)
            board[r][c] = char

            if not next_node.children:
                del node.children[char]  # prune dead branches

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)

        return result

Explanation:
Insert all words into a trie. DFS from every cell, walking the trie in sync with the board path. Key optimizations:

1. Store the full word at end nodes — collect matches immediately.
2. Mark visited cells with #, restore on backtrack.
3. Prune trie branches once exhausted — avoids revisiting dead paths.

The trie lets you share prefixes across words and bail out as soon as no trie child matches the next letter.

Time: O(M · N · 4^L) with heavy pruning · Space: O(total word chars)

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        word_set = set(words)
        rows, cols = len(board), len(board[0])
        result: set[str] = set()

        def dfs(r: int, c: int, path: str) -> None:
            if path in word_set:
                result.add(path)
            if len(path) >= 10:
                return

            char = board[r][c]
            board[r][c] = "#"
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                    dfs(nr, nc, path + board[nr][nc])
            board[r][c] = char

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, board[r][c])

        return list(result)

Explanation:
Store words in a hash set and backtrack, checking set membership for every path built. Works for small word lists but explores many paths that can never lead to a word — no early prefix pruning. The trie version is the interview answer for large words arrays.

Time: O(M · N · 4^L · L) · Space: O(W · L)

Problem 5: Replace Words (Leetcode:648)

Problem Statement

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Constraints:

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case letters.
• 1 <= sentence.length <= 106
• sentence consists of only lower-case letters and spaces.
• The number of words in sentence is in the range [1, 1000]
• The length of each word in sentence is in the range [1, 1000]
• Every two consecutive words in sentence will be separated by exactly one space.
• sentence does not have leading or trailing spaces.

Code and Explanation

Approach 1 — Trie (Shortest Root)Approach 2 — Hash Set of Roots

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False

class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        root = TrieNode()
        for word in dictionary:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_end = True

        def shortest_root(word: str) -> str:
            node = root
            for i, char in enumerate(word):
                if char not in node.children:
                    return word
                node = node.children[char]
                if node.is_end:
                    return word[: i + 1]
            return word

        return " ".join(shortest_root(w) for w in sentence.split())

Explanation:
Insert all roots into a trie. For each sentence word, walk the trie character by character. The first is_end node encountered is the shortest matching root (trie depth = prefix length). If no root matches, keep the original word.

Time: O(D · L + W · L) · Space: O(D · L)

class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        roots = set(dictionary)

        def shortest_root(word: str) -> str:
            for i in range(1, len(word) + 1):
                if word[:i] in roots:
                    return word[:i]
            return word

        return " ".join(shortest_root(w) for w in sentence.split())

Explanation:
Check every prefix of each word against a hash set of roots. Return the shortest match. Correct and simple; each prefix check is O(L) for hashing. The trie wins when roots share long prefixes (fewer redundant comparisons).

Time: O(W · L²) · Space: O(D · L)

Problem 6: Add and Search Word (Leetcode:211)

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters.
• word in search consist of '.' or lowercase English letters.
• There will be at most 2 dots in word for search queries.
• At most 104 calls will be made to addWord and search.

Code and Explanation

Approach 1 — Trie + DFS for WildcardsApproach 2 — List + Linear Wildcard Match

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False

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

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node: TrieNode, i: int) -> bool:
            if i == len(word):
                return node.is_end
            char = word[i]
            if char == ".":
                return any(dfs(child, i + 1) for child in node.children.values())
            if char not in node.children:
                return False
            return dfs(node.children[char], i + 1)

        return dfs(self.root, 0)

Explanation:
Insert words into a trie normally. For search, DFS through the trie:

1. At a literal character, follow that single child.
2. At '.', try all children (backtracking).
3. At end of pattern, require is_end.

With at most 2 dots, branching stays manageable. The trie structure avoids scanning every stored word.

Time: O(L) add · O(26^d · L) search with d wildcards · Space: O(total chars)

class WordDictionary:
    def __init__(self):
        self.words: list[str] = []

    def addWord(self, word: str) -> None:
        self.words.append(word)

    def search(self, word: str) -> bool:
        def matches(stored: str) -> bool:
            if len(stored) != len(word):
                return False
            return all(w == s or w == "." for w, s in zip(word, stored))

        return any(matches(w) for w in self.words)

Explanation:
Store words in a list and compare each one character-by-character, treating . as a wildcard. Simple but O(N · L) per search. The trie + DFS approach scales better as the dictionary grows.

Time: O(L) add · O(N · L) search · Space: O(N · L)

Problem 7: Maximum XOR of Two Numbers in an Array (Leetcode:421)

Problem Statement

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 231 - 1

Code and Explanation

Approach 1 — Binary TrieApproach 2 — Brute Force (Small Inputs)

class TrieNode:
    def __init__(self):
        self.children: list[TrieNode | None] = [None, None]

class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        root = TrieNode()
        max_bit = max(nums).bit_length()

        for num in nums:
            node = root
            for i in range(max_bit - 1, -1, -1):
                bit = (num >> i) & 1
                if node.children[bit] is None:
                    node.children[bit] = TrieNode()
                node = node.children[bit]

        best = 0
        for num in nums:
            node = root
            curr = 0
            for i in range(max_bit - 1, -1, -1):
                bit = (num >> i) & 1
                want = 1 - bit  # opposite bit maximizes XOR
                if node.children[want] is not None:
                    curr = (curr << 1) | 1
                    node = node.children[want]
                else:
                    curr <<= 1
                    node = node.children[bit]
            best = max(best, curr)

        return best

Explanation:
A binary trie stores each number's bits from MSB to LSB. To maximize XOR with a given number, greedily pick the opposite bit at each trie level when available.

1. Insert all numbers bit-by-bit into the trie.
2. For each number, walk the trie preferring the opposite bit.
3. Track the maximum XOR found.

This is the classic trie variant — same prefix-tree idea, but branches are 0 and 1.

Time: O(N · B) where B = 32 · Space: O(N · B)

class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        best = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                best = max(best, nums[i] ^ nums[j])
        return best

Explanation:
Try every pair and track the max XOR. O(N²) — only viable for tiny arrays. The binary trie reduces this to O(N · B) and is the intended solution at scale.

Time: O(N²) · Space: O(1)

Problem 8: Search Suggestions System (Leetcode:1268)

Problem Statement

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Explanation: The only word "havana" will be always suggested while typing the search word.

Constraints:

• 1 <= products.length <= 1000
• 1 <= products[i].length <= 3000
• 1 <= sum(products[i].length) <= 2 * 104
• All the strings of products are unique.
• products[i] consists of lowercase English letters.
• 1 <= searchWord.length <= 1000
• searchWord consists of lowercase English letters.

Code and Explanation

Approach 1 — Trie + DFS Collect Top 3Approach 2 — Sort + Binary Search

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.suggestions: list[str] = []

class Solution:
    def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]:
        root = TrieNode()

        for product in sorted(products):
            node = root
            for char in product:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                if len(node.suggestions) < 3:
                    node.suggestions.append(product)

        result: list[list[str]] = []
        node = root
        for char in searchWord:
            if char not in node.children:
                result.append([])
                node = None
                break
            node = node.children[char]
            result.append(node.suggestions)

        while len(result) < len(searchWord):
            result.append([])

        return result

Explanation:
Sort products lexicographically, then insert into a trie. At each node along the insert path, append the product to a suggestions list (cap at 3). Because products are inserted in sorted order, each node's list is automatically the three lexicographically smallest matches for that prefix.

Typing searchWord is just walking the trie one character at a time.

Time: O(P · L + S) · Space: O(P · L)

import bisect

class Solution:
    def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]:
        products.sort()
        result: list[list[str]] = []
        prefix = ""

        for char in searchWord:
            prefix += char
            i = bisect.bisect_left(products, prefix)
            suggestions = []
            j = i
            while j < len(products) and products[j].startswith(prefix) and len(suggestions) < 3:
                suggestions.append(products[j])
                j += 1
            result.append(suggestions)

        return result

Explanation:
Sort products once. For each typed character, binary-search the start of the prefix range, then scan forward (at most 3 items). No trie needed, but each step does O(log P + 3) work. The trie precomputes suggestions for O(1) lookup per character.

Time: O(P log P + S log P) · Space: O(P)

Problem 9: Count Prefixes of a Given String (Leetcode:2255)

Problem Statement

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

Return the number of strings in words that are a prefix of s.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Example 1:

Input: words = ["a","b","c","ab","bc","abc"], s = "abc"
Output: 3
Explanation:
The strings in words which are a prefix of s = "abc" are:
"a", "ab", and "abc".
Thus the number of strings in words which are a prefix of s is 3.

Example 2:

Input: words = ["a","a"], s = "aa"
Output: 2
Explanation:
Both of the strings are a prefix of s.
Note that the same string can occur multiple times in words, and it should be counted each time.

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length, s.length <= 10
• words[i] and s consist of lowercase English letters only.

Code and Explanation

Approach 1 — Trie Prefix WalkApproach 2 — Direct Prefix Check

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.count = 0

class Solution:
    def countPrefixes(self, words: list[str], s: str) -> int:
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.count += 1

        total = 0
        node = root
        for char in s:
            if char not in node.children:
                break
            node = node.children[char]
            total += node.count

        return total

Explanation:
Insert each word into a trie, incrementing count at the terminal node (handles duplicates). Walk s character by character through the trie, adding each node's count along the way. Each increment represents one word in words that is a prefix of s.

Time: O(W · L + |s|) · Space: O(W · L)

class Solution:
    def countPrefixes(self, words: list[str], s: str) -> int:
        return sum(1 for w in words if s.startswith(w))

Explanation:
For each word, check if s starts with it using built-in startswith. With tiny constraints (length ≤ 10), this one-liner is perfectly fine. The trie approach shines when you query many different strings against the same word list.

Time: O(W · L) · Space: O(1)