Word Break（dp)

Given anon-emptystring_s_and a dictionary_wordDict_containing a list ofnon-emptywords, determine if_s_can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.

• You may assume the dictionary does not contain duplicate words.

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"]

分析

dfs会超时 用DP

dp[i]以I结尾的word 能不能分：dp[i] = dp[j] && s[j:i] in wordDict 遇到true就断了不要继续了

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            return False
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(0, i):
                if s[j:i] in wordDict:
                    dp[i] = dp[j]
                    if dp[i]:
                        break #有合法值就出来！！！！
        return dp[n]