Word Break

Given a string s and a list of words forming a dictionary, decide whether s can be segmented into a sequence of one or more dictionary words. Words may be reused any number of times.

Example#

For s = “leetcode” and wordDict = [“leet”, “code”], the answer is true because “leet” + “code” covers the string. For s = “catsandog” and wordDict = [“cats”, “dog”, “sand”, “and”, “cat”], the answer is false: no clean split exists.

Brute force note#

Recursively trying every prefix that is a dictionary word and recursing on the rest works but revisits the same suffixes exponentially. For strings with many overlapping prefixes this blows up quickly.

Optimal approach#

Let dp[i] be true if the first i characters of s can be segmented. dp[0] is true (empty string). For each end index i, check every split point j less than i: if dp[j] is true and the substring s[j:i] is in the dictionary, then dp[i] is true. Use a set for O(1) word lookups. The answer is dp[len(s)].

 1def word_break(s, word_dict):
 2    words = set(word_dict)
 3    n = len(s)
 4    dp = [False] * (n + 1)
 5    dp[0] = True
 6    for i in range(1, n + 1):
 7        for j in range(i):
 8            if dp[j] and s[j:i] in words:
 9                dp[i] = True
10                break
11    return dp[n]
12
13
14print(word_break("leetcode", ["leet", "code"]))                       # True
15print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))  # False

Complexity#

Time is O(n squared times L) where n is the string length and L is the average substring length for slicing and hashing. Space is O(n) for the dp array plus the word set.

This is a segmentation DP that reuses subproblem results. Study the technique on the dynamic programming topic page, then continue through the 60-day curriculum.