Word Break II (All Sentences)

📋

Word Break II (All Sentences)

Edge cases:

</>

IDE

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

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    # Write your solution here
    pass

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

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

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

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

Common Bugs to Avoid

Wrong: Only one segmentation returned instead of all valid segmentationsGreedy approach returning only first valid segmentation found.✅ Explore all prefixes at each recursion step and memoize results to collect all valid segmentations.

Wrong: Partial segmentations missing due to off-by-one substring errorsIncorrect substring slicing or memoization keys.✅ Carefully handle substring indices and memo keys to include all valid segmentations.

Wrong: Non-empty output for input with no valid segmentationIncorrect base case handling or returning default non-empty list.✅ Return empty list if no valid segmentation found after exploring all prefixes.

Wrong: Timeout on large inputBrute force recursion without memoization causing exponential time.✅ Implement memoized recursion or bottom-up DP to reduce time complexity to O(n^3).

✓

Test Cases

Try testing your solution on empty and minimal inputs to catch base case bugs.

Consider tricky inputs that cause greedy or off-by-one errors.

Think about the time complexity and how memoization or DP can improve performance.

t1_01basic

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

Expected["cat sand dog","cats and dog"]

⏱ Performance - must finish in 2000ms

The string can be segmented as "cats and dog" or "cat sand dog" using the dictionary words.

💡 Think about breaking the string into prefixes that are in the dictionary and recursively solving for the suffix.

💡 Use memoization to avoid recomputing results for the same substring start index.

💡 Return all combinations by concatenating prefix with sentences from suffix, adding spaces appropriately.

Why it failed: Failed to find all valid segmentations or missed memoization causing timeout. Fix by caching results for each start index and exploring all valid prefixes.

✓ Correctly returns all valid segmentations using memoized backtracking.

t1_02basic

Input{"s":"pineapplepenapple","wordDict":["apple","pen","applepen","pine","pineapple"]}

Expected["pine apple pen apple","pine applepen apple","pineapple pen apple"]

⏱ Performance - must finish in 2000ms

Multiple valid segmentations exist using overlapping dictionary words like 'applepen' and 'apple'.

💡 Check all prefixes that match dictionary words and recurse on the remaining substring.

💡 Memoize results for each start index to avoid recomputation.

💡 Combine prefix with each sentence from suffix with a space in between.

Why it failed: Missed some valid segmentations due to greedy or incomplete search. Fix by exploring all prefixes and memoizing results.

✓ All valid segmentations found with correct memoized backtracking.

t2_01edge

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

Expected[]

⏱ Performance - must finish in 2000ms

Empty string input returns empty list as no segmentation is needed or possible.

💡 Consider what the base case should return when the input string is empty.

💡 Check if your code returns [''] or [] for empty input and adjust accordingly.

💡 Return empty list for empty input to match problem expectations.

Why it failed: Returned [''] or non-empty list for empty input. Fix by returning [] when input string is empty.

✓ Correctly returns empty list for empty input string.

t2_02edge

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

Expected["a"]

⏱ Performance - must finish in 2000ms

Single character string equal to a dictionary word returns list with that word only.

💡 Check if your code handles single character strings correctly.

💡 Ensure that if the entire string is a dictionary word, it is returned as a valid segmentation.

💡 Return list containing the string itself if it is in the dictionary.

Why it failed: Failed to return the single word when string equals dictionary word. Fix by checking full string prefix in dictionary.

✓ Correctly returns single word segmentation for single character input.

t2_03edge

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

Expected[]

⏱ Performance - must finish in 2000ms

String with no valid segmentation returns empty list.

💡 Verify that your code returns empty list when no segmentation is possible.

💡 Check that all prefixes are tried and if none lead to full segmentation, return empty list.

💡 Return empty list if no valid segmentation found after exploring all prefixes.

Why it failed: Returned non-empty list despite no valid segmentation. Fix by ensuring to return empty list if no valid sentences found.

✓ Correctly returns empty list when no segmentation is possible.

t2_04edge

Input{"s":"apple","wordDict":["apple","app","le"]}

Expected["apple"]

⏱ Performance - must finish in 2000ms

String equals a dictionary word returns list with that word only, despite substrings also in dictionary.

💡 Check if your code returns the whole string as a valid segmentation if it is in the dictionary.

💡 Ensure substrings do not prevent returning the full word segmentation.

💡 Return all valid segmentations including the full word.

Why it failed: Missed full word segmentation due to substring confusion. Fix by including full string prefix check.

✓ Correctly returns full word segmentation along with others if valid.

t3_01corner

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

Expected["aaa aaaa","aaaa aaa"]

⏱ Performance - must finish in 2000ms

Tests greedy trap: must explore all segmentations, not just first match.

💡 Avoid greedy approach that picks first matching prefix only.

💡 Use backtracking with memoization to explore all valid prefixes at each step.

💡 Return all combinations by concatenating prefix with suffix results.

Why it failed: Greedy approach returns only one segmentation. Fix by exploring all prefixes and memoizing results.

✓ All valid segmentations found by exhaustive memoized backtracking.

t3_02corner

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

Expected["a b cd","abc d"]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in substring indices and memoization boundaries.

💡 Carefully handle substring indices when checking prefixes.

💡 Ensure memoization keys correspond to start indices correctly.

💡 Return all valid segmentations by combining prefix and suffix results.

Why it failed: Off-by-one error causes missing segmentations or index errors. Fix substring slicing and memo keys.

✓ Correct substring handling and memoization produce all valid segmentations.

t3_03corner

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

Expected["a a a a a a a","a a a a a aa","a a a a aa a","a a a a aaa","a a a aa a a","a a a aa aa","a a a aaa a","a a aa a a a","a a aa a aa","a a aa aa a","a a aa aaa","a a aaa a a","a a aaa aa","a aa a a a a","a aa a a aa","a aa a aa a","a aa a aaa","a aa aa a a","a aa aa aa","a aa aaa a","a aaa a a a","a aaa a aa","a aaa aa a","a aaa aaa","aa a a a a a","aa a a a aa","aa a a aa a","aa a a aaa","aa a aa a a","aa a aa aa","aa a aaa a","aa aa a a a","aa aa a aa","aa aa aa a","aa aa aaa","aa aaa a a","aa aaa aa","aaa a a a a","aaa a a aa","aaa a aa a","aaa a aaa","aaa aa a a","aaa aa aa","aaa aaa a"]

⏱ Performance - must finish in 2000ms

Tests handling of multiple overlapping dictionary words and large branching factor.

💡 Memoize results to avoid exponential recomputation.

💡 Explore all prefixes that match dictionary words at each step.

💡 Combine prefix with all suffix segmentations to generate full results.

Why it failed: Fails due to missing memoization or pruning, causing timeout or incomplete results. Fix by caching and exploring all prefixes.

✓ All valid segmentations found efficiently with memoized backtracking.

t4_01performance

Input{"s":"aaaaaaaaaaaaaaaaaaaa","wordDict":["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=20 with dictionary words of lengths 1 to 10. Algorithm must run in O(n^3) time to avoid TLE.

💡 Brute force exponential approach will time out on this input.

💡 Use memoization to cache results for each start index.

💡 Avoid recomputing segmentations for the same substring multiple times.

Why it failed: TLE due to exponential brute force recursion without memoization. Fix by implementing memoized recursion or DP.

✓ Efficient memoized or DP solution runs within time limit.

Practice

1. You are given a string and need to find the longest contiguous substring that reads the same forwards and backwards. Which approach guarantees an optimal solution with polynomial time complexity?

easy

A. Greedy approach that expands from the first character and tries to extend the palindrome

B. Dynamic programming that builds a table to track palindromic substrings of increasing length

C. Brute force checking all substrings and verifying palindrome property each time

D. Longest common subsequence between the string and its reverse

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest contiguous palindrome substring, not subsequence, so LCS is incorrect.

2. Step 2: Evaluate approaches

   Brute force is correct but inefficient (O(n^3)). Greedy fails on many cases. DP tabulation guarantees O(n^2) time and correctness by building from smaller substrings.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP tabulation is classic for longest palindromic substring [OK]

Hint: DP tabulation tracks palindromes by substring length [OK]

Common Mistakes:

• Confusing substring with subsequence
• Assuming greedy can find longest palindrome
• Using LCS which finds subsequence, not substring

2. You need to determine if a given input string matches a pattern that includes '.' which matches any single character, and '*' which matches zero or more of the preceding element. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming using a 2D table or space-optimized 1D array

B. Sorting the pattern and string then comparing character by character

C. Backtracking with pruning based on character classes

D. Greedy matching scanning the string once from left to right

Solution

1. Step 1: Understand problem constraints

   The pattern includes '*' which can match zero or more of the preceding element, and '.' which matches any single character. This requires checking multiple matching possibilities.

2. Step 2: Identify algorithmic approach

   Greedy or sorting approaches fail because '*' can match variable-length substrings and '.' matches any character. Backtracking is exponential in worst case. Dynamic Programming efficiently stores intermediate results to avoid recomputation, guaranteeing optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles overlapping subproblems and variable-length matches [OK]

Hint: DP handles variable-length '*' matches optimally [OK]

Common Mistakes:

• Assuming greedy works for '*' patterns

3. The following code attempts to implement the space-optimized LCS algorithm. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: for j in range(1, n + 1): # iterating forwards

B. Line 5: for i in range(1, m + 1):

C. Line 9: if text1[i - 1] == text2[j - 1]:

D. Line 12: prev = temp

Solution

1. Step 1: Identify iteration order in inner loop

   The inner loop iterates forwards (j=1 to n), which causes dp[j-1] to be overwritten before it is used in the max calculation.

2. Step 2: Understand impact of forward iteration

   Because dp[j-1] is updated before dp[j], the algorithm uses updated values instead of previous iteration's values, leading to incorrect LCS length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inner loop must iterate backwards to preserve dp[j-1] values [OK]

Hint: Inner loop must run backwards to avoid overwriting dp array [OK]

Common Mistakes:

• Iterating inner loop forwards in space optimized DP
• Mixing up indices in character comparison
• Incorrect initialization of prev variable

4. Suppose you want to count the number of distinct subsequences of t in s, but now characters in s can be reused multiple times (i.e., you can use the same character in s multiple times to form subsequences). Which modification to the DP approach correctly solves this variant?

hard

A. Use a 2D DP where dp[i][j] counts subsequences using first i chars of s and j chars of t, but allow reusing s[i] by not incrementing i on match

B. Change the recurrence to allow staying at the same i index when matching characters

C. Use the same DP but iterate j forward instead of backward in the inner loop

D. No change needed; original DP already counts subsequences with reuse

Solution

1. Step 1: Understand reuse means characters in s can be used multiple times

   Original DP assumes each character in s can be used at most once per subsequence.

2. Step 2: Modify DP to allow reusing s[i]

   Use 2D DP where dp[i][j] counts subsequences using first i chars of s for first j chars of t, and when s[i] matches t[j], allow staying at i (not incrementing) to reuse character.

3. Step 3: Recognize that iterating j forward or no change won't handle reuse correctly

   Only explicit state allowing reuse by not advancing i on match works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Allowing reuse requires 2D DP with careful state transitions [OK]

Hint: Reuse means allowing same s[i] multiple times, so must not always increment i

Common Mistakes:

• Assuming original DP handles reuse
• Trying to fix by changing iteration order only

5. Suppose you want to compute the edit distance where characters can be replaced multiple times (reuse allowed) and the cost of replacement depends on character pairs. Which modification to the classic DP approach correctly handles this variant?

hard

A. Use bottom-up DP with a cost matrix for replacements and update dp accordingly

B. Modify DP to allow revisiting states multiple times with memoization

C. Switch to a greedy approach that picks cheapest replacement at each mismatch

D. Use the same DP but add a third dimension for replacement cost per character pair

Solution

1. Step 1: Understand replacement cost depends on character pairs

   Replacement cost varies, so DP must incorporate a cost matrix for each character pair.

2. Step 2: Adapt bottom-up DP to use cost matrix in dp updates

   When characters differ, dp[j] updates using the specific replacement cost from the matrix, ensuring correct minimal cost.

3. Step 3: Confirm approach handles reuse and varying costs

   Bottom-up DP with cost matrix correctly accumulates minimal costs allowing multiple replacements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP with cost matrix handles variable replacement costs [OK]

Hint: Incorporate cost matrix into DP transitions for variable replacements [OK]

Common Mistakes:

• Adding extra DP dimension unnecessarily
• Using memoization without cost matrix
• Trying greedy which fails globally