Recursion & DP Target: 15s
dp[i] = can s[:i] be segmented? Try every split point j where dp[j] is True and s[j:i] is a word.
def wordBreak(s, wordDict):
words = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
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]Type it from memory. Go.