Beyond awesome | 越而胜己

We solve this type of problems with dynamic programming. Let dp[i] be the boolean whether s[0..i-1] can be broken into valid words in wordList, then we have dp[i] = any(dp[j] and (s[j..i-1] in wordList)) for 0 <= j <= i, i.e. whether we can find some index j that is less than or equal to i such that s[0..j-1] can be split into words and s[j..i-1] is also a valid word. Specially, we assign dp[0] = true, as we do not need to worry about an empty string not being in wordList.

The 1D DP algorithm uses $\O(n)$ space. Since we need to traverse the previous part of the array for every index, the time complexity is $\O(n^2)$.

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[0] = True
words = set(wordDict)
for i in range(1, len(s)+1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[len(s)]