Word Break Problem
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Tags: Dynamic Programming
Try It!
Discussion
Video
Solution
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False for i in range(len(s) + 1)]
dp[0] = True
for c in range(len(s) + 1):
for word in wordDict:
if c >= len(word):
if dp[c - len(word)] and s[c - len(word):c] == word:
dp[c] = True
return dp[-1]