Description
Determine whether a string can be segmented into dictionary words, allowing repeated use of a word.
Solution
def word_break(s, wordDict):
dp = [True] + [False]*len(s)
for end in range(1,len(s)+1):
for word in wordDict:
if len(word) <= end and dp[end-len(word)] and s.startswith(word,end-len(word)):
dp[end] = True
break
return dp[-1]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["applepenapple",["apple","pen"]]- Output
true
apple, pen, apple covers the full string.
Example 2
- Input
["cats",["cat"]]- Output
false
The trailing s cannot be covered.
Example 3
- Input
["aaaa",["aa"]]- Output
true
The same dictionary word aa may be used twice.
Approach
Mark reachable prefix lengths. From each end position, check words that could complete a reachable shorter prefix.
Time & space
O(n d k) time; O(n) auxiliary space, where n is the string length, d is the number of dictionary words, and k their maximum length.