Word Break (Trie Approach)

📋

Problem

Imagine you have a dictionary of valid words and a long string typed without spaces. You want to check if the string can be segmented into a sequence of dictionary words, like auto-correcting a sentence typed without spaces.

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. You may reuse dictionary words any number of times.

1 ≤ s.length ≤ 10^51 ≤ wordDict.length ≤ 10^41 ≤ wordDict[i].length ≤ 20s and wordDict[i] consist of only lowercase English letters

Edge cases: Empty string s → true (empty segmentation)Dictionary contains single character words → segmentation possible if all chars in dictString s with repeated characters not in dictionary → false

</>

IDE

def wordBreak(s: str, wordDict: list[str]) -> bool:public boolean wordBreak(String s, List<String> wordDict)bool wordBreak(string s, vector<string> wordDict)function wordBreak(s, wordDict)

def wordBreak(s, wordDict):
    # Write your solution here
    pass

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // Write your solution here
        return false;
    }
}

#include <vector>
#include <string>
using namespace std;

bool wordBreak(string s, vector<string> wordDict) {
    // Write your solution here
    return false;
}

function wordBreak(s, wordDict) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseMissing memoization causes exponential recursion and early false returns.✅ Add memo dictionary to cache results for each start index.

Wrong: trueGreedy approach returns true prematurely without checking all segmentations.✅ Implement full DP or memoized recursion exploring all prefixes.

Wrong: falseFails empty string base case by returning false instead of true.✅ Return true immediately if input string is empty.

Wrong: trueIncorrect substring indexing causes partial matches to be accepted.✅ Correct substring end indices to be exclusive and verify full prefix matches.

✓

Test Cases

Focus on handling empty strings and single-character dictionary words correctly.

Beware of greedy traps and overlapping prefixes; use memoization.

Optimize your solution to run in O(n*m) time using trie and DP.

t1_01basic

Input{"s":"leetcode","wordDict":["leet","code"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The string can be segmented as "leet code" which are both in the dictionary.

💡 Try checking prefixes of the string against the dictionary.

💡 Use a trie or a set to quickly verify if a prefix is a valid word.

💡 Use memoization or DP to avoid recomputing segmentation for the same substring.

Why it failed: Failed basic segmentation: likely missing memoization or incorrect prefix checks. Fix by verifying prefixes against dictionary and caching results.

✓ Correctly segments the canonical example using trie or memoized recursion.

t1_02basic

Input{"s":"applepenapple","wordDict":["apple","pen"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The string can be segmented as "apple pen apple" which are all in the dictionary.

💡 Check all prefixes and recurse on the remaining substring.

💡 Use a trie or set to quickly check dictionary membership.

💡 Memoize results to avoid exponential time complexity.

Why it failed: Incorrect output due to missing reuse of dictionary words or no memoization. Fix by allowing repeated use of dictionary words and caching results.

✓ Correctly handles multiple segments with repeated dictionary words.

t2_01edge

Input{"s":"","wordDict":["a","b"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty string can be segmented trivially (empty segmentation).

💡 Consider the base case when the input string is empty.

💡 An empty string should return true as it requires no segmentation.

💡 Return true immediately if the string length is zero.

Why it failed: Fails empty string base case by returning false or error. Fix by returning true when s is empty.

✓ Correctly returns true for empty input string.

t2_02edge

Input{"s":"aaaaa","wordDict":["a"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

String of repeated single character 'a' can be segmented into multiple 'a's from dictionary.

💡 Check if repeated use of single-character dictionary words is handled.

💡 Ensure the algorithm allows reuse of dictionary words multiple times.

💡 Memoize results to avoid redundant computations on repeated characters.

Why it failed: Fails to reuse dictionary words multiple times causing false negative. Fix by allowing repeated use and memoizing results.

✓ Correctly segments repeated single-character words.

t2_03edge

Input{"s":"aaaaa","wordDict":["b"]}

Expectedfalse

⏱ Performance - must finish in 2000ms

String contains characters not in dictionary, so segmentation is impossible.

💡 Check if the algorithm correctly returns false when no prefixes match.

💡 Verify that the trie or dictionary lookup fails for all prefixes.

💡 Ensure no false positives from partial matches or empty prefixes.

Why it failed: Incorrectly returns true despite no matching dictionary words. Fix by confirming prefix matches strictly and returning false if none found.

✓ Correctly returns false when no dictionary words match.

t3_01corner

Input{"s":"catsandog","wordDict":["cats","dog","sand","and","cat"]}

Expectedfalse

⏱ Performance - must finish in 2000ms

No segmentation possible because 'og' is not in dictionary and no valid segmentation covers entire string.

💡 Check if your algorithm tries all possible segmentations instead of greedy.

💡 Greedy approach may fail here; use DP or memoized recursion.

💡 Ensure you explore all prefixes and backtrack properly.

Why it failed: Fails due to greedy segmentation stopping early. Fix by implementing full DP or memoized recursion exploring all prefixes.

✓ Correctly returns false for greedy trap case.

t3_02corner

Input{"s":"aaaaaaa","wordDict":["aaaa","aaa"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Segmentation possible by combining 'aaa' and 'aaaa' in multiple ways.

💡 Check if your solution handles overlapping prefixes correctly.

💡 Trie must branch properly to represent multiple prefixes.

💡 Memoize results to avoid recomputation of overlapping segments.

Why it failed: Fails due to incorrect trie handling of overlapping prefixes or missing memoization. Fix by building trie with branching and caching results.

✓ Correctly segments string with overlapping prefixes.

t3_03corner

Input{"s":"aaaaaaa","wordDict":["aaaa","aaa"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Same as t3_02 but tests off-by-one errors in substring indexing.

💡 Verify substring indices carefully to avoid off-by-one errors.

💡 Check that end indices in substring calls are exclusive.

💡 Ensure trie traversal and DP indices align correctly.

Why it failed: Fails due to off-by-one errors in substring or trie traversal. Fix by correcting substring end indices and DP indexing.

✓ Correctly handles substring indexing and trie traversal.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input string length n=100000 with dictionary size up to 10000 and max word length 20. Algorithm must run in O(n*m) time within 2 seconds.

💡 Use trie with memoized recursion or iterative DP to achieve O(n*m) complexity.

💡 Avoid brute force recursion which is exponential and will time out.

💡 Preprocess dictionary into trie for efficient prefix checks.

Why it failed: TLE due to brute force recursion or lack of memoization. Fix by implementing trie-based DP or memoized recursion.

✓ Efficient O(n*m) solution passes performance test.

Practice

1. You are given an array of integers and a range [low, high]. You need to count the number of pairs (i, j) with i < j such that the XOR of nums[i] and nums[j] lies within the given range. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a brute force nested loop to check all pairs and count those with XOR in the range.

B. Use dynamic programming to store counts of XOR values for prefixes and combine them.

C. Sort the array and use two pointers to find pairs with XOR in the range.

D. Build a bitwise trie of the numbers and for each number, query how many previously inserted numbers produce XOR less than or equal to a limit, then combine results for the range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting pairs with XOR in a range efficiently, which brute force (nested loops) is too slow for large inputs.

2. Step 2: Identify the suitable data structure

   A bitwise trie allows efficient counting of numbers with XOR less than a limit by traversing bits from most significant to least significant.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitwise trie approach is known to solve XOR range queries optimally [OK]

Hint: Bitwise trie enables efficient XOR range counting [OK]

Common Mistakes:

• Thinking sorting + two pointers works for XOR ranges
• Assuming DP can handle XOR pairs directly
• Believing brute force is optimal

2. You need to design a data structure that efficiently supports insertion of strings, exact search for strings, and prefix-based search queries. Which of the following data structures guarantees optimal time complexity for these operations regardless of the number of stored strings?

easy

A. Hash Set storing all strings for O(1) average search but no efficient prefix search

B. Trie (Prefix Tree) that stores characters in nodes with links to children nodes

C. Sorting all strings and using binary search for prefix queries

D. Using a balanced binary search tree keyed by entire strings

Solution

1. Step 1: Understand operation requirements

   Insertion, exact search, and prefix search must be efficient. Hash sets provide O(1) average search but cannot efficiently support prefix queries.

2. Step 2: Compare data structures

   Tries store characters in nodes allowing O(m) time for insert/search/startsWith, where m is length of word or prefix. Binary search on sorted strings is O(m log n) and BSTs do not support prefix queries efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie supports prefix queries in O(m) time [OK]

Hint: Tries enable prefix queries in O(m) time [OK]

Common Mistakes:

• Confusing hash sets as supporting prefix queries efficiently

3. Given the following code snippet implementing the trie-based autocomplete, and the input products = ["mobile", "mouse", "moneypot"] and searchWord = "mo", what is the value of the variable result after processing the entire searchWord?

easy

A. [["mobile", "moneypot", "mouse"], ["moneypot", "mobile", "mouse"]]

B. [["mobile", "moneypot", "mouse"], ["mobile", "moneypot", "mouse"]]

C. [["mobile", "mouse", "moneypot"], ["mobile", "mouse", "moneypot"]]

D. [["mobile", "mouse", "moneypot"], ["mouse", "mobile", "moneypot"]]

Solution

1. Step 1: Sort products lexicographically

   Sorted products: ["mobile", "moneypot", "mouse"]

2. Step 2: Build trie and collect suggestions

   For prefix 'm': suggestions are ["mobile", "moneypot", "mouse"]. For prefix 'mo': same suggestions as all start with 'mo'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Result matches expected suggestions for prefixes 'm' and 'mo' [OK]

Hint: Sorted products determine suggestion order at each prefix [OK]

Common Mistakes:

• Mixing order of suggestions
• Off-by-one in prefix traversal
• Appending suggestions after node moves

4. What is the time complexity of the optimal offline approach that sorts the array and queries, then uses a bit trie to answer maximum XOR queries with constraints?

medium

A. O(n * q)

B. O(n * log M + q * log M)

C. O((n + q) * log M), where M is the max number in nums

D. O(n * log n + q * log q)

Solution

1. Step 1: Identify sorting cost

   Sorting nums and queries costs O(n log n + q log q), but dominated by trie operations.

2. Step 2: Analyze trie insertion and query

   Each insertion and query takes O(log M) where M is max number; total O(n log M + q log M).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting plus trie operations sum to O(n log M + q log M) [OK]

Hint: Trie operations cost O(log M) per element/query [OK]

Common Mistakes:

• Confusing n*q brute force with trie approach
• Ignoring log M factor
• Assuming sorting dominates complexity

5. Suppose the problem is modified so that words can be reused multiple times to form longer words (e.g., prefixes can be repeated). Which modification to the trie + BFS approach correctly handles this variant?

hard

A. No change needed; the existing BFS approach already handles reuse of words.

B. Modify BFS to enqueue child nodes even if child.word is None, allowing repeated prefixes.

C. Use DFS with memoization to explore repeated prefixes and avoid cycles.

D. Replace trie with a graph where edges represent possible concatenations and run BFS.

Solution

1. Step 1: Understand reuse of words

   Allowing reuse means prefixes can be repeated multiple times, potentially causing cycles in traversal.

2. Step 2: Why DFS with memoization is needed

   DFS with memoization prevents infinite loops by caching results for nodes, correctly handling repeated prefixes and cycles.

3. Step 3: Why other options fail

   Existing BFS assumes no reuse; enqueuing nodes without word breaks prefix condition; graph BFS without cycle handling risks infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DFS + memoization handles repeated prefixes safely [OK]

Hint: Reuse requires cycle-safe DFS with memoization [OK]

Common Mistakes:

• Assuming BFS handles reuse without changes
• Enqueueing invalid nodes breaks prefix rules
• Ignoring cycles in graph representation