What happens if you not using memoization in recursion?

Leads to exponential time and TLE on large inputs Fix: Add memo dictionary to cache results for start indices

What happens if you checking prefixes without efficient data structure?

Repeated substring checks slow down solution Fix: Use trie to quickly check prefixes instead of substring lookups

What happens if you incorrect base case handling (not returning true for empty string)?

Algorithm returns false even when segmentation is possible Fix: Return true when start index reaches string length

What happens if you not breaking early when dp[i] is true in iterative dp?

Unnecessary computations increase runtime Fix: Break inner loop once dp[i] is set true

Interview PreptriesmediumAmazonFacebookGoogleBloomberg

Word Break (Trie Approach)

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumTRIEAmazonFacebookGoogle

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.

💡 This problem involves segmenting a string into valid dictionary words. Beginners often struggle because the naive approach tries all segmentations, leading to exponential time. Using tries helps efficiently check prefixes, and memoization avoids repeated work, making the solution scalable.

📋

Problem Statement

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

💡

Example

Input"s = \"leetcode\", wordDict = [\"leet\", \"code\"]"

Outputtrue

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

Input"s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]"

Outputtrue

The string can be segmented as "apple pen apple".

Input"s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]"

Outputfalse

No segmentation of the string into dictionary words is possible.

Empty string s → true (empty segmentation)
Dictionary contains single character words → segmentation possible if all chars in dict
String s with repeated characters not in dictionary → false
Dictionary with overlapping prefixes → ensure trie handles prefix branching correctly

⚠️

Common Mistakes

Not using memoization in recursion

Leads to exponential time and TLE on large inputs

✅ Add memo dictionary to cache results for start indices

Checking prefixes without efficient data structure

Repeated substring checks slow down solution

✅ Use trie to quickly check prefixes instead of substring lookups

Incorrect base case handling (not returning true for empty string)

Algorithm returns false even when segmentation is possible

✅ Return true when start index reaches string length

Not breaking early when dp[i] is true in iterative DP

Unnecessary computations increase runtime

✅ Break inner loop once dp[i] is set true

Building trie incorrectly (e.g., missing is_word flag)

Prefix checks fail to identify complete words, causing false negatives

✅ Mark end of each inserted word with is_word = True

🧠

Brute Force (Pure Recursion)

💡 This approach tries every possible prefix split recursively. It is simple and helps understand the problem but is inefficient due to repeated work and exponential time.

Intuition

Try every prefix of the string; if the prefix is in the dictionary, recursively check the remaining suffix. If any segmentation works, return true.

Algorithm

Start from index 0 of the string.
For each possible end index from start+1 to end of string:
Check if substring from start to end is in the dictionary.
If yes, recursively check if the rest of the string can be segmented.
If any recursive call returns true, return true; else false.

💡 The recursion tree grows exponentially because each prefix choice leads to multiple suffix checks, making it hard to see the inefficiency at first.

</>

Code

class Solution:
    def wordBreak(self, s, wordDict):
        word_set = set(wordDict)
        def backtrack(start):
            if start == len(s):
                return True
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set and backtrack(end):
                    return True
            return False

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.wordBreak("leetcode", ["leet", "code"]))  # True
    print(sol.wordBreak("applepenapple", ["apple", "pen"]))  # True
    print(sol.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))  # False

Line Notes

word_set = set(wordDict)Convert list to set for O(1) membership checks to speed up prefix lookups

def backtrack(start):Define recursive function to check segmentation from index start

if start == len(s):Base case: reached end means successful segmentation of entire string

for end in range(start + 1, len(s) + 1):Try all possible prefixes starting at start index

if s[start:end] in word_set and backtrack(end):If prefix is in dictionary and suffix can be segmented, return True

return FalseNo valid segmentation found from this start index

import java.util.*;
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        return backtrack(s, 0, wordSet);
    }
    private boolean backtrack(String s, int start, Set<String> wordSet) {
        if (start == s.length()) return true;
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordSet.contains(s.substring(start, end)) && backtrack(s, end, wordSet)) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wordBreak("leetcode", Arrays.asList("leet", "code"))); // true
        System.out.println(sol.wordBreak("applepenapple", Arrays.asList("apple", "pen"))); // true
        System.out.println(sol.wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat"))); // false
    }
}

Line Notes

Set<String> wordSet = new HashSet<>(wordDict);Use HashSet for fast lookup of dictionary words

private boolean backtrack(String s, int start, Set<String> wordSet)Recursive helper to check segmentation from start index

if (start == s.length()) return true;Base case: entire string segmented successfully

for (int end = start + 1; end <= s.length(); end++)Try all prefixes starting at start

if (wordSet.contains(s.substring(start, end)) && backtrack(s, end, wordSet))If prefix in dictionary and suffix valid, return true

return false;No valid segmentation found from this start index

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        return backtrack(s, 0, wordSet);
    }
private:
    bool backtrack(const string& s, int start, unordered_set<string>& wordSet) {
        if (start == s.size()) return true;
        for (int end = start + 1; end <= s.size(); ++end) {
            if (wordSet.count(s.substr(start, end - start)) && backtrack(s, end, wordSet)) {
                return true;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<string> dict1 = {"leet", "code"};
    cout << boolalpha << sol.wordBreak("leetcode", dict1) << endl; // true
    vector<string> dict2 = {"apple", "pen"};
    cout << sol.wordBreak("applepenapple", dict2) << endl; // true
    vector<string> dict3 = {"cats", "dog", "sand", "and", "cat"};
    cout << sol.wordBreak("catsandog", dict3) << endl; // false
    return 0;
}

Line Notes

unordered_set<string> wordSet(wordDict.begin(), wordDict.end());Initialize hash set for O(1) lookups of dictionary words

bool backtrack(const string& s, int start, unordered_set<string>& wordSet)Recursive function to check segmentation from start index

if (start == s.size()) return true;Base case: full segmentation achieved

for (int end = start + 1; end <= s.size(); ++end)Try all prefixes starting at start

if (wordSet.count(s.substr(start, end - start)) && backtrack(s, end, wordSet))If prefix in dictionary and suffix valid, return true

return false;No valid segmentation found from this start index

var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    function backtrack(start) {
        if (start === s.length) return true;
        for (let end = start + 1; end <= s.length; end++) {
            if (wordSet.has(s.substring(start, end)) && backtrack(end)) {
                return true;
            }
        }
        return false;
    }
    return backtrack(0);
};

// Test cases
console.log(wordBreak("leetcode", ["leet", "code"])); // true
console.log(wordBreak("applepenapple", ["apple", "pen"])); // true
console.log(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false

Line Notes

const wordSet = new Set(wordDict);Use Set for O(1) membership checks of dictionary words

function backtrack(start)Recursive helper to check segmentation from start index

if (start === s.length) return true;Base case: entire string segmented successfully

for (let end = start + 1; end <= s.length; end++)Try all prefixes starting at start

if (wordSet.has(s.substring(start, end)) && backtrack(end))If prefix in dictionary and suffix valid, return true

return false;No valid segmentation found from this start index

⏱

Complexity

TimeO(2^n) in worst case

SpaceO(n) recursion stack

At each index, we try all possible prefixes, leading to an exponential number of recursive calls.

💡 For n=20, this means potentially over a million calls, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's nature and why optimization is needed.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(2^n)`	`O(n) recursion stack`	Yes (deep recursion)	Yes	Mention only - never code
2. Memoized Recursion with Trie	`O(n * m)`	`O(n + trie size)`	No (memo reduces calls)	Yes	Good to code if comfortable with recursion and tries
3. Iterative DP with Trie	`O(n * m)`	`O(n + trie size)`	No	Yes	Preferred approach for clean iterative solution

Practice

(1/5)

1. Consider the following buggy Trie insert method. Which line contains the subtle bug that causes search to fail for inserted words?

medium

A. Line where node = self.root is assigned

B. Line where node = node.children[ch] is assigned inside the loop

C. Line where isEnd flag should be set but is missing

D. Line where the if condition checks if ch not in node.children

2. The following code attempts to implement the optimal StreamChecker. Identify the single line that contains a subtle bug that can cause incorrect results or inefficiency.

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in word:  # Bug here: words not reversed
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

medium

A. Line: for ch in word:

B. Line: if len(self.stream) > self.max_len:

C. Line: for ch in reversed(self.stream):

D. Line: if node.is_word:

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Identify missing isEnd flag set

Step 2: Understand impact on search

Final Answer:

Quick Check:

Solution

Step 1: Identify how trie is built

Step 2: Understand impact on query

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse of words

Step 2: Why DFS with memoization is needed

Step 3: Why other options fail

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse allowance

Step 2: Modify search and add_word accordingly

Step 3: Why other options fail

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse allows cycles

Step 2: Add depth limit to DFS

Final Answer:

Quick Check:

Ready to prove it?