000139-Word-Break

Problem

https://leetcode.com/problems/word-break/description/

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.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

Constraints:

1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique.

Solution

DP problem

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        # max length of a word in the wordDict
        w_max_len = max(map(len, wordDict))
        print(dp)
        print(w_max_len)
        for i in range(1, n+1):
            if dp[i]:
                continue
            for j in range(i-1, max(i-w_max_len-1, -1), -1):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
            print(dp)
        return dp[n]

# Example "catsanddog", wordDict = ["cats","dog","sand","and","cat"]
# dp = [True, False, False, False, False, False, False, False, False, False]
# w_max_len = 4 (sand) 
# cat -> i = 3, dp[3] = True
# cats -> i = 4 dp[4] = True
# sand -> i = 7 dp[7] = True
# dog -> i = 9 dp[9] = False
# dp = [True, False, False, True, True, False, False, True, False, False] 
# --> dp[9] = False