Trie

Master this topic with zero to advance depth.

Trie: The Prefix Powerhouse

A Trie (pronounced "try"), also known as a Prefix Tree, is a specialized tree-based data structure used for efficient retrieval of keys in a large dataset of strings. Unlike a standard binary search tree, no node in the trie stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.

1. Core Operations & Complexity

Trie operations are highly efficient, with time complexity scales with the length of the string ( $L$ ), not the number of keys ( $N$ ).

Operation	Description	Time Complexity	Space Complexity
`Insert(word)`	Add a word to the trie.	$O(L)$	$O(N \times L)$ worst case
`Search(word)`	Check if a word exists in the trie.	$O(L)$	$O(1)$
`StartsWith(pre)`	Check if any word starts with prefix `pre`.	$O(L)$	$O(1)$

2. Why Use a Trie Over a Hash Map?

While Hash Maps offer $O(L)$ search on average, Tries provide unique advantages:

Prefix Searching: Tries can find all keys with a common prefix in $O(L + K)$ time ( $K$ is the number of matches).
Ordered Traversal: Keys can be retrieved in alphabetical order easily.
Space Efficiency: Tries can save space when many keys share long common prefixes.
No Hash Collisions: Tries avoid the overhead and worst-case $O(N)$ scenarios of hash tables.

3. Implementation Patterns

Array vs. HashMap for Children

Array [26]: Fastest access ( $O(1)$ to find child), but space-intensive if the alphabet is large or the trie is sparse.
HashMap: More space-efficient for sparse trees or large character sets (e.g., Unicode), but slightly slower due to hashing overhead.

4. Key Signals in Interviews:

Autocomplete/Typeahead: Suggesting words as the user types.
Longest Common Prefix: Finding the shared beginning of multiple strings.
Wildcard Matching: Searching for words with missing characters (e.g., s.r).
Bitwise XOR: Binary Tries (storing bits) are used to find maximum XOR pairs in $O(32)$ per query.

Implement Trie (Prefix Tree)

Implement a trie which supports insert, search, and startsWith operations.

Medium

Examples

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

Approach 1

Level I: HashMap-based Trie

Intuition

Flexible implementation using a HashMap for children, suitable for any character set (Unicode).

⏱ O(L)💾 O(N * L)

Detailed Dry Run

Insert 'apple': R -> a -> p -> p -> l -> e (end).

java

import java.util.*;
class Trie {
    class Node { Map<Character, Node> children = new HashMap<>(); boolean isEnd = false; }
    Node root = new Node();
    public void insert(String w) { Node c=root; for(char x:w.toCharArray()) { c.children.putIfAbsent(x, new Node()); c=c.children.get(x); } c.isEnd=true; }
    public boolean search(String w) { Node n=find(w); return n!=null && n.isEnd; }
    public boolean startsWith(String p) { return find(p)!=null; }
    private Node find(String s) { Node c=root; for(char x:s.toCharArray()) { c=c.children.get(x); if(c==null) return null; } return c; }
}

Approach 2

Level III: Array-based Trie (Optimal)

Intuition

Static array [26] for lowercase English. Fastest possible access with minimal memory overhead for dense tries.

⏱ O(L)💾 O(N * L * 26)

Detailed Dry Run

Insert 'cat': root.children['c'-'a'] -> node1.children['a'-'a'] -> node2.children['t'-'a'] -> node3(isEnd=true).

java

class Trie {\n    class Node { Node[] children = new Node[26]; boolean isEnd = false; }\n    Node root = new Node();\n    public void insert(String w) { Node c=root; for(char x:w.toCharArray()) { int i=x-'a'; if(c.children[i]==null) c.children[i]=new Node(); c=c.children[i]; } c.isEnd=true; }\n    public boolean search(String w) { Node n=find(w); return n!=null && n.isEnd; }\n    public boolean startsWith(String p) { return find(p)!=null; }\n    private Node find(String s) { Node c=root; for(char x:s.toCharArray()) { int i=x-'a'; if(c.children[i]==null) return null; c=c.children[i]; } return c; }\n}

Add and Search Word

Design a data structure that supports adding new words and finding if a string matches any previously added string, including wildcard character '.' matching.

Medium

Examples

Input: addWord("bad"), addWord("dad"), search(".ad")
Output: true, true, true

Approach 1

Level III: Trie + DFS (Optimal)

Intuition

Standard Trie implementation. When encountering '.', perform DFS to check all possible children of the current node.

⏱ Add: O(L), Search: O(26^L) worst case.💾 O(N * L * 26).

Detailed Dry Run

Search '.ad': Root -> dfs('.'). Try 'a'-'z'. 'b' exists. From 'b', dfs('ad') -> matches 'ad' and isEnd=true. Return true.

java

class WordDictionary {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    Node root = new Node();
    public void addWord(String w) { Node c=root; for(char x:w.toCharArray()) { int i=x-'a'; if(c.children[i]==null) c.children[i]=new Node(); c=c.children[i]; } c.isEnd=true; }
    public boolean search(String w) { return dfs(w, 0, root); }
    private boolean dfs(String w, int i, Node n) {
        if(n==null) return false; if(i==w.length()) return n.isEnd;
        char x=w.charAt(i);
        if(x=='.') { for(Node child:n.children) if(dfs(w, i+1, child)) return true; return false; }
        return dfs(w, i+1, n.children[x-'a']);
    }
}

Map Sum Pairs

Calculate sum of all values whose key starts with a specific prefix.

Medium

Approach 1

Level III: Trie with Pre-calculated Sums (Optimal)

Intuition

Each trie node stores the sum of values for all words passing through it. When updating a key, we first find its old value to calculate the delta and update all nodes in the path.

⏱ Insert: O(L), Sum: O(L).💾 O(N * L * 26).

Detailed Dry Run

Insert('apple', 3): Nodes a,p,p,l,e each get +3 sum. Insert('app', 2): Nodes a,p,p get +2. Sum('ap') -> 5.

java

import java.util.*;
class MapSum {
    class Node { Node[] children = new Node[26]; int sum = 0; }
    Node root = new Node();
    Map<String, Integer> map = new HashMap<>();
    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        Node curr = root;
        for(char c : key.toCharArray()) {
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new Node();
            curr = curr.children[i];
            curr.sum += delta;
        }
    }
    public int sum(String prefix) {
        Node curr = root;
        for(char c : prefix.toCharArray()) {
            curr = curr.children[c - 'a'];
            if(curr == null) return 0;
        }
        return curr.sum;
    }
}

Replace Words

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 successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".\n\nGiven a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Medium

Examples

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

Approach 1

Level I: HashSet of Roots

Intuition

Store all roots in a HashSet. For each word in the sentence, check every possible prefix (starting from length 1) in the HashSet. Return the first match found.

⏱ O(SentenceLength * WordLength^2)💾 O(DictionaryLength * RootLength)

Detailed Dry Run

Word: 'cattle'. Check 'c', 'ca', 'cat'. 'cat' is in HashSet. Replace 'cattle' with 'cat'.

java

import java.util.*;
class Solution {
    public String replaceWords(List<String> roots, String sentence) {
        Set<String> set = new HashSet<>(roots);
        StringBuilder res = new StringBuilder();
        for(String word : sentence.split(" ")) {
            String prefix = "";
            for(int i=1; i<=word.length(); i++) {
                prefix = word.substring(0, i);
                if(set.contains(prefix)) break;
            }
            if(res.length()>0) res.append(" ");
            res.append(prefix);
        }
        return res.toString();
    }
}

Approach 2

Level III: Trie (Optimal)

Intuition

Build a Trie from the roots. For each word in the sentence, traverse the Trie. The first isEndOfWord node encountered provides the shortest root.

⏱ O(DictionaryLength * RootLength + SentenceLength)💾 O(DictionaryLength * RootLength)

Detailed Dry Run

Trie: root -> c -> a -> t (end). Word: 'cattle'. Traverse c -> a -> t (found end). Return 'cat'.

java

class Solution {
    class Node { Node[] children = new Node[26]; boolean isEnd; }
    Node root = new Node();
    public String replaceWords(List<String> dictionary, String sentence) {
        for (String s : dictionary) { Node curr = root; for (char c : s.toCharArray()) { int i = c - 'a'; if (curr.children[i] == null) curr.children[i] = new Node(); curr = curr.children[i]; } curr.isEnd = true; }
        StringBuilder res = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (res.length() > 0) res.append(" ");
            Node curr = root; StringBuilder prefix = new StringBuilder();
            for (char c : word.toCharArray()) {
                int i = c - 'a'; if (curr.children[i] == null || curr.isEnd) break;
                prefix.append(c); curr = curr.children[i];
            }
            res.append(curr.isEnd ? prefix.toString() : word);
        }
        return res.toString();
    }
}

Word Search II

The Challenge of Multiple Words

If we have $K$ words, running a standard Word Search (DFS) for each word takes $O(K \cdot M \cdot N \cdot 3^L)$ . This is inefficient because many words share prefixes (e.g., 'apple' and 'apply').

Trie for Prefix Sharing

By storing the dictionary in a Trie, we can search for all words simultaneously. As we traverse the grid in DFS, we also traverse the Trie. If a path in the grid doesn't match any prefix in the Trie, we prune the search immediately.

Optimization: Trie Pruning

Once a word is found, we can remove it from the Trie (or mark it as found) and potentially delete leaf nodes that are no longer part of any other words. This drastically reduces the search space for subsequent cells.

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. Includes visual Trie-based pruning trace. The same letter cell may not be used more than once in a word.

Hard

Examples

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"]

Approach 1

Level I: Naive DFS (Multiple Word searches)

Intuition

Iterate through each word in the list and perform a standard DFS search on the board.

For each word in words, scan every cell (r, c). If board[r][c] == word[0], start a DFS to find the rest of the characters.

⏱ O(K * M * N * 3^L) where K is number of words, L is max length.💾 O(L) for recursion depth.

Detailed Dry Run

Searching 'oath'. Find 'o' at (0,0). Neighbors: (0,1) 'a'. Next: (1,1) 't'. Next (0,1) NO, (0,2) NO, (1,0) NO... SUCCESS.

java

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (exist(board, word)) result.add(word);
        }
        return result;
    }
    private boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                if (dfs(board, i, j, word, 0)) return true;
        return false;
    }
    private boolean dfs(char[][] board, int r, int c, String word, int i) {
        if (i == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(i)) return false;
        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, r+1, c, word, i+1) || dfs(board, r-1, c, word, i+1) || 
                        dfs(board, r, c+1, word, i+1) || dfs(board, r, c-1, word, i+1);
        board[r][c] = temp;
        return found;
    }
}

Approach 2

Level II: Backtracking with Trie

Intuition

Insert all words into a Trie. Traverse the board and the Trie simultaneously to find matches.

Starting at each cell, if the character exists as a child of the Trie root, move into the Trie. If node.isEndOfWord, add the word to result.

⏱ O(M * N * 3^L)💾 O(Total chars in words) for Trie.

Detailed Dry Run

Trie: root -> o -> a -> t -> h (END). At (0,0) 'o': matches root.child('o'). Neighbors of (0,0): 'a' at (0,1) matches 'o'.child('a'). Neighbors of (0,1): 't' at (1,1) matches 'a'.child('t')...

java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null;
}
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode curr = root;
            for (char c : w.toCharArray()) {
                if (curr.children[c - 'a'] == null) curr.children[c - 'a'] = new TrieNode();
                curr = curr.children[c - 'a'];
            }
            curr.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                dfs(board, i, j, root, res);
        return res;
    }
    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> res) {
        char ch = board[r][c];
        if (node.children[ch - 'a'] == null) return;
        node = node.children[ch - 'a'];
        if (node.word != null) {
            res.add(node.word);
            node.word = null;
        }
        board[r][c] = '#';
        int[] dr = {0, 0, 1, -1}, dc = {1, -1, 0, 0};
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && board[nr][nc] != '#')
                dfs(board, nr, nc, node, res);
        }
        board[r][c] = ch;
    }
}

Approach 3

Level III: Optimized Trie (Node Removal)

Intuition

When a leaf node is found and its word is extracted, if it has no children, we can delete the node from its parent to avoid re-visiting dead branches.

Add a parent pointer or count to each node. When word != "", set it to null. If children count becomes 0, remove the entry from search path completely.

⏱ O(M * N * 3^L) with significantly better early exit.💾 O(Total chars).

Detailed Dry Run

Trie: root -> o -> a -> t -> h (END). After finding 'oath', the path 'h' -> 't' -> 'a' -> 'o' is pruned if no other words use them. Subsequent board scans will skip 'o' immediately.

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; String word = null; }
    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node curr = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (curr.children[i] == null) curr.children[i] = new Node();
                curr = curr.children[i];
            }
            curr.word = w;
        }
        List<String> result = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) dfs(board, r, c, root, result);
        }
        return result;
    }
    private void dfs(char[][] board, int r, int c, Node node, List<String> res) {
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'a'] == null) return;
        node = node.children[ch - 'a'];
        if (node.word != null) { res.add(node.word); node.word = null; }
        board[r][c] = '#';
        int[] dr = {0, 0, 1, -1}, dc = {1, -1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) dfs(board, nr, nc, node, res);
        }
        board[r][c] = ch;
    }
}

Design Search Autocomplete System

Design a search autocomplete system for a search engine. Users may input a sentence (at least one character and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that have a prefix the same as the part of the sentence already typed.

Visual Representation

Typed: "i"
Prefix "i" matches "i love you" (5), "island" (3), "ironman" (2).
Return: ["i love you", "island", "ironman"]

Typed: " " (space)
Prefix "i " matches "i love you" (5), "i a cool" (2).
Return: ["i love you", "i a cool"]

Hard

Examples

Input: ["AutocompleteSystem", "input", "input", "input", "input"]
[[["i love you", "island", "ironman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
Output: [null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]

Approach 1

Level I: HashMap (Brute Force Prefix Search)

Intuition

Maintain a HashMap of historical sentences and their counts. For every input, iterate through the entire map, collect sentences starting with the prefix, and sort them to find the top 3. Simple but O(N * L) per query.

⏱ O(N * L) per query.💾 O(N * L)

java

import java.util.*;
class AutocompleteSystem {
    Map<String, Integer> counts = new HashMap<>();
    String prefix = "";
    public AutocompleteSystem(String[] s, int[] t) { for(int i=0; i<s.length; i++) counts.put(s[i], t[i]); }
    public List<String> input(char c) {
        if(c == '#') { counts.put(prefix, counts.getOrDefault(prefix, 0)+1); prefix=""; return new ArrayList<>(); }
        prefix += c; List<String> res = new ArrayList<>();
        for(String s : counts.keySet()) if(s.startsWith(prefix)) res.add(s);
        Collections.sort(res, (a, b) -> counts.get(a).equals(counts.get(b)) ? a.compareTo(b) : counts.get(b)-counts.get(a));
        return res.size() > 3 ? res.subList(0, 3) : res;
    }
}

Approach 2

Level III: Trie + Top-3 Cache

Intuition

Store each historical sentence in a Trie. Each node stores a list of the top 3 hot sentences passing through it. Update these lists incrementally to ensure O(1) query time (just return the list at the current node).

⏱ O(L) per character typed.💾 O(N * L)

java

import java.util.*;
class AutocompleteSystem {
    class Node { Map<String, Integer> counts = new HashMap<>(); List<String> top3 = new ArrayList<>(); Node[] children = new Node[128]; }
    Node root = new Node(), curr = root;
    StringBuilder sb = new StringBuilder();
    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) insert(sentences[i], times[i]);
    }
    private void insert(String s, int k) {
        Node n = root;
        for (char c : s.toCharArray()) {
            if (n.children[c] == null) n.children[c] = new Node();
            n = n.children[c];
            n.counts.put(s, n.counts.getOrDefault(s, 0) + k);
            List<String> list = new ArrayList<>(n.counts.keySet());
            Collections.sort(list, (a, b) -> n.counts.get(a).equals(n.counts.get(b)) ? a.compareTo(b) : n.counts.get(b) - n.counts.get(a));
            if (list.size() > 3) list = list.subList(0, 3);
            n.top3 = list;
        }
    }
    public List<String> input(char c) {
        if (c == '#') { insert(sb.toString(), 1); sb.setLength(0); curr = root; return new ArrayList<>(); }
        sb.append(c);
        if (curr != null) curr = curr.children[c];
        return curr == null ? new ArrayList<>() : curr.top3;
    }
}

Word Squares

Given an array of unique strings words, return all the word squares you can build from words. The same word from words can be used multiple times. A sequence of words forms a valid word square if the kth row and kth column read the exact same string for each 0 <= k < max(numRows, numColumns).

Hard

Examples

Input: words = ["area","lead","wall","lady","ball"]
Output: [["wall","area","lead","lady"],["ball","area","lead","lady"]]

Approach 1

Level I: Brute Force Backtracking

Intuition

Try all possible word combinations recursively. At each step, check if the current partial square is valid. Very slow as it doesn't use the prefix property effectively.

⏱ O(N^L) where N is words, L is length.💾 O(L)

java

class Solution {
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> res = new ArrayList<>();
        if (words == null || words.length == 0) return res;
        int n = words[0].length();
        for (String w : words) {
            List<String> list = new ArrayList<>(); list.add(w);
            backtrack(res, list, words, n);
        }
        return res;
    }
    private void backtrack(List<List<String>> res, List<String> list, String[] words, int n) {
        if (list.size() == n) { res.add(new ArrayList<>(list)); return; }
        int idx = list.size();
        StringBuilder sb = new StringBuilder();
        for (String s : list) sb.append(s.charAt(idx));
        String prefix = sb.toString();
        for (String word : words) {
            if (word.startsWith(prefix)) {
                list.add(word); backtrack(res, list, words, n); list.remove(list.size()-1);
            }
        }
    }
}

Approach 2

Level III: Trie + Backtracking

Intuition

At each step k, we need to find words that start with a specific prefix. This prefix is formed by the characters at position k of the words already chosen. A Trie is the perfect data structure to quickly fetch all words sharing a common prefix.

⏱ O(N * 26^L)💾 O(Total Chars)

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; List<String> wordList = new ArrayList<>(); }
    public List<List<String>> wordSquares(String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node curr = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (curr.children[i] == null) curr.children[i] = new Node();
                curr = curr.children[i];
                curr.wordList.add(w);
            }
        }
        List<List<String>> res = new ArrayList<>();
        int n = words[0].length();
        for (String w : words) {
            List<String> square = new ArrayList<>();
            square.add(w); backtracking(1, n, square, root, res);
        }
        return res;
    }
    private void backtracking(int step, int n, List<String> square, Node root, List<List<String>> res) {
        if (step == n) { res.add(new ArrayList<>(square)); return; }
        StringBuilder prefix = new StringBuilder();
        for (String s : square) prefix.append(s.charAt(step));
        Node curr = root;
        for (char c : prefix.toString().toCharArray()) {
            if (curr.children[c-'a'] == null) return;
            curr = curr.children[c-'a'];
        }
        for (String candidate : curr.wordList) {
            square.add(candidate); backtracking(step + 1, n, square, root, res); square.remove(square.size()-1);
        }
    }
}

Maximum XOR of Two Numbers in an Array

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

Visual Representation

Nums: [3, 10, 5, 25, 2, 8]
Max XOR: 5 XOR 25 = 28

Binary Trie approach:
1. Insert all numbers as 32-bit binary strings into a Trie.
2. For each number X, find a path that maximizes XOR.
3. To maximize XOR, at each bit, try to go to the opposite bit (if curr is 0, try 1).
   If opposite exists, result |= (1 << bit).

Medium

Examples

Input: nums = [3,10,5,25,2,8]
Output: 28

Approach 1

Level I: Brute Force

Intuition

Check every pair of numbers $(i, j)$ in the array and calculate their XOR. Keep track of the maximum XOR found. Simple but $O(N^2)$ .

⏱ O(N^2)💾 O(1)

java

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++)
            for (int j = i; j < nums.length; j++) max = Math.max(max, nums[i] ^ nums[j]);
        return max;
    }
}

Approach 2

Level III: Binary Trie

Intuition

Represent each number as a 31-bit or 32-bit binary string. Insert all numbers into a Trie where each node has at most two children (0 and 1). For each number $X$ , we want to find a number $Y$ such that $X \oplus Y$ is maximized. At each bit $i$ of $X$ , if the $i$ -th bit is $b$ , we prioritize moving to a child representing $1-b$ in the Trie. This greedy choice at each bit ensures the maximum possible XOR value.

⏱ O(N * 31) = O(N).💾 O(N * 31).

java

class Solution {
    class Node { Node[] children = new Node[2]; }
    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        for (int n : nums) {
            Node curr = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[bit] == null) curr.children[bit] = new Node();
                curr = curr.children[bit];
            }
        }
        int max = 0;
        for (int n : nums) {
            Node curr = root; int val = 0;
            for (int i = 31; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[1 - bit] != null) { val |= (1 << i); curr = curr.children[1 - bit]; }
                else curr = curr.children[bit];
            }
            max = Math.max(max, val);
        }
        return max;
    }
}

Camelcase Matching

A query word matches a given pattern if we can insert lowercase letters to the pattern so that it equals the query. Return a list of booleans.

Visual Representation

Queries: ["FooBar", "FooBarTest", "FootBall"]
Pattern: "FB"

"FooBar" -> F-oo-B-ar -> Matches!
"FooBarTest" -> F-oo-B-ar-T-est -> Extra 'T' (Uppercase) -> Fails!

Medium

Examples

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

Approach 1

Level I: Two Pointers (Standard Search)

Intuition

For each word, use two pointers to check if the pattern is a subsequence. Additionally, ensure that any uppercase letters in the word that are NOT in the pattern cause a mismatch.

⏱ O(N * L) where N is words, L is word length.💾 O(1)

java

class Solution {
    public List<Boolean> camelMatch(String[] words, String pattern) {
        List<Boolean> res = new ArrayList<>();
        for (String w : words) res.add(check(w, pattern));
        return res;
    }
    private boolean check(String w, String p) {
        int i = 0;
        for (char c : w.toCharArray()) {
            if (i < p.length() && c == p.charAt(i)) i++;
            else if (Character.isUpperCase(c)) return false;
        }
        return i == p.length();
    }
}

Approach 2

Level III: Two Pointers / Trie

Intuition

For each query, use two pointers ( $i$ for query, $j$ for pattern). If $query[i] == pattern[j]$ , increment both. If $query[i]$ is lowercase, increment only $i$ . If $query[i]$ is uppercase and doesn't match $pattern[j]$ , it's a mismatch. After the loop, if $j$ reached pattern length and no extra uppercase letters remain in query, it's a match.

⏱ O(N * L).💾 O(1) extra space.

java

import java.util.*;
class Solution {
    public List<Boolean> camelMatch(String[] queries, String pattern) {
        List<Boolean> res = new ArrayList<>();
        for (String q : queries) res.add(match(q, pattern));
        return res;
    }
    private boolean match(String q, String p) {
        int j = 0;
        for (char c : q.toCharArray()) {
            if (j < p.length() && c == p.charAt(j)) j++;
            else if (Character.isUpperCase(c)) return false;
        }
        return j == p.length();
    }
}

Prefix and Suffix Search

Design a data structure that allows searching for a word with a given prefix AND a given suffix. If there are multiple valid words, return the largest index.

Visual Representation

Words: ["apple"]
Suffix#Prefix construction: "e#apple", "le#apple", "ple#apple", ...
Insert these into a Trie. 

Query: prefix="ap", suffix="le"
Search Trie for "le#ap". 
Found node stores max index: 0.

Hard

Examples

Input: ["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output: [null, 0]

Approach 1

Level I: HashMap (All Combinations)

Intuition

Pre-calculate all potential prefix + '#' + suffix combinations for every word and store them in a HashMap with their index. Query is O(1). Inefficient space but simple.

⏱ Pre: O(N * L^2), Query: O(1).💾 O(N * L^2)

java

class WordFilter {
    Map<String, Integer> map = new HashMap<>();
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            for (int p = 0; p <= words[i].length(); p++) {
                for (int s = 0; s <= words[i].length(); s++) {
                    map.put(words[i].substring(0, p) + "#" + words[i].substring(words[i].length()-s), i);
                }
            }
        }
    }
    public int f(String prefix, String suffix) {
        return map.getOrDefault(prefix + "#" + suffix, -1);
    }
}

Approach 2

Level III: Wrapped Trie ({suffix}#{prefix})

Intuition

To handle both prefix and suffix in a single search, we can insert multiple variations of each word into the Trie. For a word like 'apple', insert: '#apple', 'e#apple', 'le#apple', 'ple#apple', 'pple#apple', 'apple#apple'. A query with prefix 'a' and suffix 'le' becomes a prefix search for 'le#a' in this special Trie.

⏱ Initialization: O(N * L^2), Search: O(L).💾 O(N * L^2).

java

import java.util.*;
class WordFilter {
    class Node { Node[] children = new Node[27]; int weight; }
    Node root = new Node();
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String w = "{" + words[i];
            insert(w, i);
            for (int j = words[i].length() - 1; j >= 0; j--) {
                w = words[i].charAt(j) + w;
                insert(w, i);
            }
        }
    }
    private void insert(String s, int weight) {
        Node curr = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) curr.children[idx] = new Node();
            curr = curr.children[idx]; curr.weight = weight;
        }
    }
    public int f(String prefix, String suffix) {
        Node curr = root;
        for (char c : (suffix + "{" + prefix).toCharArray()) {
            if (curr.children[c - 'a'] == null) return -1;
            curr = curr.children[c - 'a'];
        }
        return curr.weight;
    }
}

Word Ladder II

Given two words, beginWord and endWord, and a dictionary wordList, return all shortest transformation sequences from beginWord to endWord. Only one letter can be changed at a time.

Hard

Examples

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Approach 1

Level I: Standard BFS (Shortest Transformation)

Intuition

Use a standard BFS to find the shortest distance from beginWord to endWord. In each step, change one character at a time and check if it exists in the dictionary. This approach only finds the length of the shortest path, not the actual paths themselves.

⏱ O(N * L * 26)💾 O(N * L)

java

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return new ArrayList<>();
        Queue<List<String>> q = new LinkedList<>();
        q.add(Arrays.asList(beginWord));
        List<List<String>> res = new ArrayList<>();
        Set<String> visited = new HashSet<>(); visited.add(beginWord);
        boolean found = false;
        while (!q.isEmpty() && !found) {
            int size = q.size();
            Set<String> localVisited = new HashSet<>();
            for (int i = 0; i < size; i++) {
                List<String> path = q.poll();
                String last = path.get(path.size() - 1);
                for (String next : neighbors(last, dict)) {
                    if (next.equals(endWord)) {
                        found = true; List<String> newPath = new ArrayList<>(path);
                        newPath.add(next); res.add(newPath);
                    } else if (!visited.contains(next)) {
                        localVisited.add(next); List<String> newPath = new ArrayList<>(path);
                        newPath.add(next); q.add(newPath);
                    }
                }
            }
            visited.addAll(localVisited);
        }
        return res;
    }
    private List<String> neighbors(String s, Set<String> dict) {
        List<String> res = new ArrayList<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                chars[i] = c; String next = new String(chars);
                if (dict.contains(next)) res.add(next);
            }
            chars[i] = old;
        }
        return res;
    }
}

Approach 2

Level III: BFS + Backtracking (Trie for Neighbors)

Intuition

Use BFS to find the shortest distance from beginWord to all reachable words. To quickly find 'neighbors' (words differing by one char), we can iterate through each position of the word and try all 26 letters, checking against a Set/Trie. Finally, use DFS to backtrack all shortest paths from beginWord to endWord using the distance levels found in BFS.

⏱ O(N * L * 26 + Paths).💾 O(N * L).

java

import java.util.*;
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return new ArrayList<>();
        Map<String, Integer> dist = new HashMap<>();
        dist.put(beginWord, 0);
        Queue<String> q = new LinkedList<>(); q.add(beginWord);
        while(!q.isEmpty()){
            String curr = q.poll();
            if(curr.equals(endWord)) break;
            for(int i=0; i<curr.length(); i++){
                char[] chars = curr.toCharArray();
                for(char c='a'; c<='z'; c++){
                    chars[i] = c; String next = new String(chars);
                    if(set.contains(next) && !dist.containsKey(next)){
                        dist.put(next, dist.get(curr) + 1); q.add(next);
                    }
                }
            }
        }
        List<List<String>> res = new ArrayList<>();
        if(!dist.containsKey(endWord)) return res;
        dfs(endWord, beginWord, dist, new LinkedList<>(Arrays.asList(endWord)), res);
        return res;
    }
    private void dfs(String curr, String target, Map<String, Integer> dist, LinkedList<String> path, List<List<String>> res) {
        if (curr.equals(target)) { List<String> copy = new ArrayList<>(path); Collections.reverse(copy); res.add(copy); return; }
        for (int i=0; i<curr.length(); i++) {
            char[] chars = curr.toCharArray();
            for (char c='a'; c<='z'; c++) {
                chars[i] = c; String next = new String(chars);
                if (dist.containsKey(next) && dist.get(next) == dist.get(curr) - 1) {
                    path.add(next); dfs(next, target, dist, path, res); path.removeLast();
                }
            }
        }
    }
}

Concatenated Words

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words. A concatenated word is defined as a string that is entirely comprised of at least two shorter words in the given array.

Visual Representation

Words: ["cat", "dog", "catdog"]

DFS(0):
1. Prefixes found: "cat" (Trie matches).
2. Remaining: "dog".
3. DFS("dog"): Prefix found: "dog". Remaining: "".
4. SUCCESS -> "catdog" is concatenated.

Hard

Examples

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

Approach 1

Level I: Set-based DFS

Intuition

Use a HashSet to store all words. For each word, check if it can be partitioned into at least two shorter words present in the Set using a recursive DFS with memoization. Simple but less space-efficient for prefix matching.

⏱ O(N * L^2)💾 O(N * L)

java

import java.util.*;
class Solution {
    Set<String> dict;
    Map<String, Boolean> memo;
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        dict = new HashSet<>(Arrays.asList(words));
        List<String> res = new ArrayList<>();
        for (String word : words) {
            dict.remove(word); // Remove current word to avoid self-concatenation
            memo = new HashMap<>();
            if (canBreak(word)) res.add(word);
            dict.add(word); // Add it back for other words
        }
        return res;
    }
    private boolean canBreak(String s) {
        if (memo.containsKey(s)) return memo.get(s);
        if (dict.contains(s)) return true;
        for (int i = 1; i < s.length(); i++) {
            String prefix = s.substring(0, i);
            if (dict.contains(prefix) && canBreak(s.substring(i))) {
                memo.put(s, true); return true;
            }
        }
        memo.put(s, false); return false;
    }
}

Approach 2

Level III: Trie + DFS + Memoization

Intuition

First, sort the words by length. This allows us to only search for a word's composition using words that were previously added to the Trie (which are guaranteed to be shorter). For each word, use DFS with a Trie to check if it can be broken into multiple pieces that are already in the Trie.

⏱ O(N * L^2) where L is max length.💾 O(N * L) for Trie.

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        List<String> res = new ArrayList<>();
        Node root = new Node();
        for (String w : words) {
            if (canForm(w, 0, root, new Boolean[w.length()])) res.add(w);
            else insert(root, w);
        }
        return res;
    }
    private boolean canForm(String w, int start, Node root, Boolean[] memo) {
        if (start == w.length()) return true;
        if (memo[start] != null) return memo[start];
        Node curr = root;
        for (int i = start; i < w.length(); i++) {
            if (curr.children[w.charAt(i)-'a'] == null) break;
            curr = curr.children[w.charAt(i)-'a'];
            if (curr.isEnd && canForm(w, i + 1, root, memo)) return memo[start] = true;
        }
        return memo[start] = false;
    }
    private void insert(Node root, String w) {
        if (w.isEmpty()) return;
        Node curr = root;
        for (char c : w.toCharArray()) {
            if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
            curr = curr.children[c-'a'];
        }
        curr.isEnd = true;
    }
}

Palindrome Pairs

Given a list of unique words, return all pairs of distinct indices (i, j) such that the concatenation of the two words words[i] + words[j] is a palindrome.

Visual Representation

Words: ["abcd", "dcba", "lls", "s", "sssll"]

Pairs:
1. "abcd" + "dcba" = "abcddcba" (Palindrome)
2. "dcba" + "abcd" = "dcbaabcd" (Palindrome)
3. "s" + "lls" = "slls" (Palindrome)
4. "sssll" + "lls" = "ssslllls" (Wait, no...)
Wait: "lls" + "s" = "llss" (No)
Actual: "sssll" + "lls" -> "ssslllls" NO.
Let's check "lls" reverse is "sll".
If we pick i="sssll", j="lls", words[i]+words[j] = "ssslllls" Fails.
Correct for "lls": s + lls = slls (Correct).

Hard

Examples

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]

Approach 1

Level I: Brute Force (Check all pairs)

Intuition

Iterate through every pair of indices $(i, j)$ in the array. Construct the string words[i] + words[j] and check if it is a palindrome. This is $O(N^2 \cdot L)$ , which is too slow for large inputs.

⏱ O(N^2 * L)💾 O(1)

java

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i == j) continue;
                if (isPal(words[i] + words[j])) res.add(Arrays.asList(i, j));
            }
        }
        return res;
    }
    boolean isPal(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}

Approach 2

Level III: Trie (Suffix-to-Prefix matching)

Intuition

For a word $W_i$ , we want to find $W_j$ such that $W_i W_j$ is a palindrome. This happens if $W_i$ can be split into $S_1 S_2$ where $S_1$ is a palindrome and $S_2$ is the reverse of $W_j$ , OR if $W_i = S_1 S_2$ where $S_2$ is a palindrome and $S_1$ is the reverse of $W_j$ . A Trie storing words in reverse allows us to efficiently find these matches.

⏱ O(N * L^2).💾 O(N * L).

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; int index = -1; List<Integer> list = new ArrayList<>(); }
    public List<List<Integer>> palindromePairs(String[] words) {
        Node root = new Node();
        for (int i = 0; i < words.length; i++) {
            String rev = new StringBuilder(words[i]).reverse().toString();
            Node curr = root;
            for (int j = 0; j < rev.length(); j++) {
                if (isPal(rev, j, rev.length() - 1)) curr.list.add(i);
                int c = rev.charAt(j) - 'a';
                if (curr.children[c] == null) curr.children[c] = new Node();
                curr = curr.children[c];
            }
            curr.index = i;
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            Node curr = root;
            for (int j = 0; j < words[i].length(); j++) {
                if (curr.index != -1 && curr.index != i && isPal(words[i], j, words[i].length() - 1)) res.add(Arrays.asList(i, curr.index));
                curr = curr.children[words[i].charAt(j) - 'a'];
                if (curr == null) break;
            }
            if (curr != null) {
                if (curr.index != -1 && curr.index != i) res.add(Arrays.asList(i, curr.index));
                for (int j : curr.list) res.add(Arrays.asList(i, j));
            }
        }
        return res;
    }
    private boolean isPal(String s, int i, int j) {
        while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
        return true;
    }
}

Shortest Unique Prefix

Given an array of words, find the shortest unique prefix of each word, such that the prefix is not a prefix of any other word.

Visual Representation

Words: ["zebra", "dog", "duck", "dove"]

Trie with counts:
root
 -> z(1) -> e(1) ... -> found count=1 at 'z'
 -> d(3) 
    -> o(2) 
       -> g(1) -> found count=1 at 'g' (prefix "dog")
       -> v(1) -> found count=1 at 'v' (prefix "dov")
    -> u(1) -> found count=1 at 'u' (prefix "du")

Hard

Examples

Input: ["zebra", "dog", "duck", "dove"]
Output: ["z", "dog", "du", "dov"]

Approach 1

Level I: Brute Force Comparison

Intuition

For each word, check every possible prefix starting from length 1. Compare this prefix against all other words. The first prefix that is not a prefix of any other word is the shortest unique prefix for that word.

⏱ O(N^2 * L)💾 O(1)

java

class Solution {
    public String[] findPrefixes(String[] words) {
        String[] result = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            String currentWord = words[i];
            for (int len = 1; len <= currentWord.length(); len++) {
                String prefix = currentWord.substring(0, len);
                boolean isUnique = true;
                for (int j = 0; j < words.length; j++) {
                    if (i == j) continue;
                    if (words[j].startsWith(prefix)) {
                        isUnique = false;
                        break;
                    }
                }
                if (isUnique) {
                    result[i] = prefix;
                    break;
                }
            }
        }
        return result;
    }
}

Approach 2

Level III: Trie (Node Visited Count)

Intuition

Insert all words into a Trie. As you insert, increment a visited count (count) for each node along the path. To find the shortest unique prefix for a word, traverse the Trie until you reach a node with count == 1. That node marks the end of the shortest unique prefix.

⏱ O(N * L).💾 O(N * L).

java

class Solution {
    class Node { Node[] children = new Node[26]; int count = 0; }
    public String[] findPrefixes(String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node curr = root;
            for (char c : w.toCharArray()) {
                if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
                curr = curr.children[c-'a']; curr.count++;
            }
        }
        String[] res = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            Node curr = root; StringBuilder sb = new StringBuilder();
            for (char c : words[i].toCharArray()) {
                sb.append(c); curr = curr.children[c-'a'];
                if (curr.count == 1) break;
            }
            res[i] = sb.toString();
        }
        return res;
    }
}

Maximum XOR with an Element from Array

Given an integer array nums, return the maximum value of nums[j] XOR xi where nums[j] <= mi. If all numbers in nums are larger than mi, the answer is -1.

Visual Representation

Nums: [0, 1, 2, 3, 4]
Query: [3, 1] (x=3, m=1)
Valid nums <= 1: [0, 1]
XOR results: 3^0=3, 3^1=2
Max: 3

Optimal approach:
1. Sort nums.
2. Sort queries by m.
3. Insert nums into Trie as long as nums[j] <= m.
4. Query Trie for max XOR.

Hard

Examples

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]

Approach 1

Level I: Brute Force

Intuition

For each query [xi, mi], iterate through every number in the nums array. If nums[j] <= mi, calculate nums[j] XOR xi and update the maximum. Simple O(N*Q) solution.

⏱ O(N * Q)💾 O(1)

java

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int max = -1;
            for (int n : nums) if (n <= queries[i][1]) max = Math.max(max, n ^ queries[i][0]);
            ans[i] = max;
        }
        return ans;
    }
}

Approach 2

Level III: Offline Queries + Binary Trie

Intuition

Since we need to check $nums[j] \le m$ , we can sort both $nums$ and $queries$ (by $m$ ). By processing queries offline in non-decreasing order of $m$ , we only insert numbers into the Trie when they become 'valid' for the current $m$ . This transforms the conditional maximum problem into a standard Maximum XOR problem on a growing Trie.

⏱ O(N log N + Q log Q + (N+Q) * 31).💾 O(N * 31).

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[2]; }
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int[][] qWithIdx = new int[queries.length][3];
        for(int i=0; i<queries.length; i++) { qWithIdx[i][0]=queries[i][0]; qWithIdx[i][1]=queries[i][1]; qWithIdx[i][2]=i; }
        Arrays.sort(qWithIdx, (a,b) -> a[1] - b[1]);
        
        int[] ans = new int[queries.length];
        Node root = new Node();
        int numsIdx = 0;
        for(int i=0; i<qWithIdx.length; i++) {
            int x = qWithIdx[i][0], m = qWithIdx[i][1], originalIdx = qWithIdx[i][2];
            while(numsIdx < nums.length && nums[numsIdx] <= m) {
                insert(root, nums[numsIdx++]);
            }
            if(numsIdx == 0) ans[originalIdx] = -1;
            else ans[originalIdx] = getMaxXor(root, x);
        }
        return ans;
    }
    private void insert(Node root, int n) {
        Node curr = root;
        for(int i=30; i>=0; i--) {
            int bit = (n >> i) & 1;
            if(curr.children[bit] == null) curr.children[bit] = new Node();
            curr = curr.children[bit];
        }
    }
    private int getMaxXor(Node root, int x) {
        Node curr = root; int res = 0;
        for(int i=30; i>=0; i--) {
            int bit = (x >> i) & 1;
            if(curr.children[1-bit] != null) { res |= (1 << i); curr = curr.children[1-bit]; }
            else curr = curr.children[bit];
        }
        return res;
    }
}

Word Break II

Given a string s and a string dictionary wordDict, return all possible sentences that can be formed by adding spaces to s such that each word is a valid dictionary word.

Visual Representation

s = "catsanddog", dict = ["cat","cats","and","sand","dog"]

Trie path 1: root -> c -> a -> t -> s (word) -> a -> n -> d (word) -> d -> o -> g (word)
Trie path 2: root -> c -> a -> t (word) -> s -> a -> n -> d (word) -> d -> o -> g (word)

Sentences:
1. "cats and dog"
2. "cat sand dog"

Hard

Examples

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Approach 1

Level I: Standard Recursion

Intuition

Iterate through the string s. If a prefix exists in the dictionary, recursively solve for the remaining suffix. O(2^N).

⏱ O(2^N)💾 O(N)

java

import java.util.*;
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict, new HashMap<>());
    }
    private List<String> dfs(String s, List<String> wordDict, Map<String, List<String>> memo) {
        if (memo.containsKey(s)) return memo.get(s);
        List<String> res = new ArrayList<>();
        if (s.isEmpty()) {
            res.add("");
            return res;
        }
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String> subList = dfs(s.substring(word.length()), wordDict, memo);
                for (String sub : subList) {
                    res.add(word + (sub.isEmpty() ? "" : " ") + sub);
                }
            }
        }
        memo.put(s, res);
        return res;
    }
}

Approach 2

Level III: Trie + DFS + Memoization

Intuition

Use a Trie to store words for fast prefix lookups. Combine DFS with memoization to store results for each starting index.

⏱ O(N * 2^N)💾 O(N * 2^N)

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; String word = null; }
    public List<String> wordBreak(String s, List<String> wordDict) {
        Node root = new Node();
        for (String w : wordDict) { Node c = root; for (char x : w.toCharArray()) { int i = x-'a'; if (c.children[i] == null) c.children[i] = new Node(); c = c.children[i]; } c.word = w; }
        return dfs(s, 0, root, new HashMap<>());
    }
    private List<String> dfs(String s, int start, Node root, Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) return memo.get(start);
        List<String> res = new ArrayList<>();
        if (start == s.length()) { res.add(""); return res; }
        Node curr = root;
        for (int i = start; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a'; if (curr.children[idx] == null) break;
            curr = curr.children[idx];
            if (curr.word != null) {
                List<String> sub = dfs(s, i + 1, root, memo);
                for (String w : sub) res.add(curr.word + (w.isEmpty() ? "" : " ") + w);
            }
        }
        memo.put(start, res); return res;
    }
}

Boggle Game

Find the maximum number of words you can find in a Boggle board such that no two words overlap (i.e., they don't share any cell).

Visual Representation

Board: ["abc", "def", "ghi"]
Words: ["abc", "defi", "gh"]

Possible Selections:
1. {"abc", "def"} -> 2 words
2. {"abc"} -> 1 word

Result: 2

Hard

Examples

Input: board = [["a","b","c"],["d","e","f"],["g","h","i"]], words = ["abc","def","gh"]
Output: 2

Approach 1

Level I: Brute Force DFS

Intuition

For each word in the dictionary, perform a standard DFS on the board to see if it exists. Keep track of used cells and try all combinations of non-overlapping words. Very slow but simple.

⏱ O(W * M * N * 4^L)💾 O(M * N)

java

// Standard DFS per word

Approach 2

Level III: Trie + Backtracking (Max Independent Sets)

Intuition

This is a variant of Word Search II. First, find all occurrences of all dictionary words on the board (Word Search II style). Then, treat this as a problem of finding the maximum number of disjoint sets (words) using backtracking. Each word is a set of cell coordinates.

⏱ O(Exp) due to backtracking for disjoint sets.💾 O(N*L)

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    int maxWords = 0;
    public int maxWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node curr = root;
            for (char c : w.toCharArray()) {
                if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
                curr = curr.children[c-'a'];
            }
            curr.isEnd = true;
        }
        List<List<int[]>> allOccurrences = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfsFindAll(board, r, c, root, new ArrayList<>(), allOccurrences);
            }
        }
        backtrackDisjoint(allOccurrences, 0, new boolean[board.length][board[0].length], 0);
        return maxWords;
    }
    private void dfsFindAll(char[][] b, int r, int c, Node n, List<int[]> path, List<List<int[]>> all) {
        char ch = b[r][c];
        if (ch == '#' || n.children[ch-'a'] == null) return;
        n = n.children[ch-'a'];
        path.add(new int[]{r, c});
        if (n.isEnd) all.add(new ArrayList<>(path));
        b[r][c] = '#';
        int[] dr = {0,0,1,-1}, dc = {1,-1,0,0};
        for (int i=0; i<4; i++) {
            int nr = r+dr[i], nc = c+dc[i];
            if (nr>=0 && nr<b.length && nc>=0 && nc<b[0].length) dfsFindAll(b, nr, nc, n, path, all);
        }
        b[r][c] = ch; path.remove(path.size()-1);
    }
    private void backtrackDisjoint(List<List<int[]>> all, int idx, boolean[][] used, int count) {
        maxWords = Math.max(maxWords, count);
        for (int i = idx; i < all.size(); i++) {
            List<int[]> word = all.get(i);
            if (canTake(word, used)) {
                mark(word, used, true);
                backtrackDisjoint(all, i + 1, used, count + 1);
                mark(word, used, false);
            }
        }
    }
    private boolean canTake(List<int[]> word, boolean[][] used) {
        for (int[] p : word) if (used[p[0]][p[1]]) return false;
        return true;
    }
    private void mark(List<int[]> word, boolean[][] used, boolean val) {
        for (int[] p : word) used[p[0]][p[1]] = val;
    }
}

Stream of Characters

Design a data structure that accepts a stream of characters and checks if any suffix of the characters queried so far is in a given list of words.

Hard

Examples

Input: words = ["cd","f","kl"], streamQueries = ["a", "b", "c", "d", "e", "f"]
Output: [false, false, false, true, false, true]

Approach 1

Level I: Brute Force Suffix Comparison

Intuition

Store all arrived characters in a list. For every query, iterate through all words in the dictionary and check if any word matches the current suffix of the character stream. O(N * L) per query.

⏱ O(N * L) per query.💾 O(Total Chars)

java

class StreamChecker {
    List<String> words; StringBuilder sb = new StringBuilder();
    public StreamChecker(String[] words) { this.words = Arrays.asList(words); }
    public boolean query(char letter) {
        sb.append(letter); String s = sb.toString();
        for (String w : words) if (s.endsWith(w)) return true;
        return false;
    }
}

Approach 2

Level III: Reverse Trie

Intuition

Since we need to match a suffix of the stream, it's efficient to store the dictionary words in a Trie in reversed order. As new characters arrive in the stream, we store them in a buffer (or current path). To check if any suffix matches, we traverse the reversed Trie starting from the last character received.

⏱ O(L) per query (L is max word length).💾 O(N * L).

java

class StreamChecker {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    Node root = new Node();
    StringBuilder sb = new StringBuilder();
    public StreamChecker(String[] words) {
        for (String w : words) {
            Node curr = root;
            for (int i = w.length() - 1; i >= 0; i--) {
                int c = w.charAt(i) - 'a';
                if (curr.children[c] == null) curr.children[c] = new Node();
                curr = curr.children[c];
            }
            curr.isEnd = true;
        }
    }
    public boolean query(char letter) {
        sb.append(letter);
        Node curr = root;
        for (int i = sb.length() - 1; i >= 0 && i >= sb.length() - 2000; i--) {
            int c = sb.charAt(i) - 'a';
            if (curr.children[c] == null) return false;
            curr = curr.children[c];
            if (curr.isEnd) return true;
        }
        return false;
    }
}

Longest Word in Dictionary through Deleting

Given a string s and a string dictionary dictionary, return the longest string in the dictionary that can be formed by deleting some characters of the given string s.

Medium

Examples

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Approach 1

Level I: Two Pointers (Standard Search)

Intuition

Iterate through each word in the dictionary. Use two pointers to check if the word is a subsequence of s. Keep track of the longest word found (using lexicographical order for ties).

⏱ O(N * L) where N is dict size.💾 O(1).

java

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String result = "";
        for (String word : dictionary) {
            if (isSubsequence(word, s)) {
                if (word.length() > result.length() || (word.length() == result.length() && word.compareTo(result) < 0)) result = word;
            }
        }
        return result;
    }
    private boolean isSubsequence(String word, String s) {
        int i = 0, j = 0;
        while (i < word.length() && j < s.length()) {
            if (word.charAt(i) == s.charAt(j)) i++;
            j++;
        }
        return i == word.length();
    }
}

Approach 2

Level III: Trie (Index-based Subsequence Search)

Intuition

Store s in a way that allows fast subsequence checks. For each character a-z, store a list of indices where it appears in s. For any word, use binary search to find the smallest valid index for the next character. A Trie of words can also be used to explore multiple words simultaneously.

⏱ O(N * L * log S).💾 O(S).

java

import java.util.*;
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String res = "";
        for (String w : dictionary) {
            if (isSub(s, w)) {
                if (w.length() > res.length() || (w.length() == res.length() && w.compareTo(res) < 0)) res = w;
            }
        }
        return res;
    }
    private boolean isSub(String s, String w) {
        int i = 0, j = 0;
        while (i < s.length() && j < w.length()) { if (s.charAt(i) == w.charAt(j)) j++; i++; }
        return j == w.length();
    }
}

Prefix and Suffix Search (Optimized Query)

The same as Prefix and Suffix Search, but focused on extreme query performance.

Hard

Approach 1

Level I: Brute Force Search

Intuition

For each query, iterate through the entire dictionary. For each word, check if it starts with the prefix and ends with the suffix. Return the maximum index found. O(N * L) per query.

⏱ O(N * L) per query.💾 O(1)

java

// O(N*L) search

Approach 2

Level III: Precomputed HashMap of Pairs

Intuition

For cases where memory is available but query speed is critical, precompute all possible (prefix, suffix) pairs for every word. Use a HashMap to store prefix + " " + suffix as the key and the max index as the value.

⏱ Query: O(1). Initialization: O(N * L^2).💾 O(N * L^2).

java

class WordFilter {
    Map<String, Integer> map = new HashMap<>();
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            for (int p = 0; p <= words[i].length(); p++) {
                String pre = words[i].substring(0, p);
                for (int s = 0; s <= words[i].length(); s++) {
                    map.put(pre + " " + words[i].substring(s), i);
                }
            }
        }
    }
    public int f(String prefix, String suffix) {
        return map.getOrDefault(prefix + " " + suffix, -1);
    }
}

← Previous TopicStack

Next Topic →Union Find

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.