Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
1 <= s.length <= 300, 1 <= wordDict.length <= 1000
DP where dp[i] = true if s[0:i] can be segmented. For each position, check if any word in dict ends at that position and dp[i - len(word)] is true.
def wordBreak(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]