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]