Word Break

Question

Given a string and a dictionary of words, determine if the string can be segmented into space-separated dictionary words. Tests dynamic programming skills, commonly asked at Meta.

Codemia · Accepted Answer

This problem can be effectively solved using dynamic programming, specifically utilizing a boolean array to track which substrings of the input string can be formed using the provided dictionary of words. The primary pattern here is to check all possible partitions of the input string and see if each partition can be matched with a word in the dictionary. We will use the DP approach where we define a DP array `dp[i]` that indicates whether the substring `s[0:i]` can be segmented into words from the dictionary.

1. Initialize a boolean array `dp` of size `n+1` (where `n` is the length of the input string `s`) with `dp[0] = True`, as an empty string can always be segmented. 
2. Iterate through the string using two nested loops: the outer loop `i` goes from 1 to `n`, and the inner loop `j` goes from 0 to `i-1`. 
3. For each `i` and `j`, check if the substring `s[j:i]` exists in the dictionary and if `dp[j]` is `True`. If both conditions are satisfied, set `dp[i] = True` and break out of the inner loop. 
4. Finally, return the value of `dp[n]`, which will indicate whether the entire string can be segmented into dictionary words.

**Example:** 
For `s = 'leetcode'` and `dict = ['leet', 'code']`, 
- Start with `dp = [True, False, ..., False]` (length 9). 
- When `i = 4`, `j = 0` checks `s[0:4]`, which is 'leet' (found in dict), so `dp[4] = True`. 
- When `i = 8`, `j = 4` checks `s[4:8]`, which is 'code' (found in dict), so `dp[8] = True`. 
- The final `dp` array will show that `dp[8]` is `True`, meaning 'leetcode' can be segmented.

```python
def wordBreak(s: str, wordDict: List[str]) -> bool:
    n = len(s)
    word_set = set(wordDict)
    dp = [False] * (n + 1)
    dp[0] = True  # base case: empty string can be segmented

for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

return dp[n]
```

The time complexity of this solution is O(n^2) because we have two nested loops: the outer loop runs `n` times and the inner loop can run up to `n` times in the worst case. The space complexity is O(n) due to the DP array storing boolean values for each substring length.

1. **Empty String**: If `s` is an empty string, the function should return `True` since an empty string can be considered as being segmented into zero words. 
2. **No Words in Dictionary**: If the dictionary is empty, the function should return `False` unless the string is also empty. 
3. **Single Character Match**: If `s` is a single character and exists in the dictionary, it should return `True`, otherwise `False`. 
4. **Long String with Repeated Segments**: For a long string composed of repeated segments of the same word, e.g., `s = 'aaaa'` with `dict = ['a', 'aa']`, the function should correctly identify that it can be segmented.

Word Break

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string