Can a string be split into dictionary words? Mark each position you can reach, building on earlier marks, until you reach the end.
▼The problem
LeetCode 139 (Medium). Given a string s and a list of dictionary words, return whether s can be split into a sequence of one or more dictionary words. A word may be used more than once.
Examples (LeetCode's own): "leetcode", ["leet", "code"] → true (leet + code); "applepenapple", ["apple", "pen"] → true (apple + pen + apple, apple used twice); "catsandog", ["cats", "dog", "sand", "and", "cat"] → false (cat + sand and cats + and both leave "og").
The solution
def wordBreak(s, wordDict):
words = set(wordDict)
n = len(s)
dp = [True] + [False] * n
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]Transcript
Word Break. Given a string and a list of words, can you split the string into dictionary words? Words may repeat.
Take leetcode, with leet and code: leet, then code. True. Apple pen apple works too, using apple twice. But cats-and-og fails: every split leaves the last two letters stranded.
The naive way tries every prefix: if it's a word, solve the rest the same way. The same suffixes get solved again and again: twenty a's and a b take nearly twenty-nine thousand calls. Thirty take three and a half million.
Instead, build a bridge. Put a post at every position and light the ones you can reach. Post zero is the start, so it's lit. Post i lights up if some lit post j has a word from j to i.
In code: a set of words and n plus one flags, only the first true. For each end i, try each start j. If j is lit and the slice is a word, light i and stop. Return the last flag.
Let's build apple pen apple. Post zero is lit. At five, apple fits from zero: light it. Six and seven stay dark. At eight, pen fits from five. Nine through twelve stay dark. At thirteen, apple fits from eight. The last lamp is lit: true.
Each of n posts tries up to n starts: n squared checks. Each slice costs up to n letters to hash, so n cubed at worst. The lamps take linear space.
Lay a word, light a lamp, and walk across. That's Word Break.