LeetCode 139. 单词拆分（DP）

示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词
     
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

class Solution {	//C++
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int i, j, n = s.size();
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        vector<bool> dp(n+1,false);//dp[j]包含第j个字符为结尾的字符能否拆分
        dp[0] = true;//空字符能拆分
        for(i = 0; i <= n; ++i)
        {
        	if(dp[i] == true)//左半边存在
	        	for(j = i+1; j <= n; ++j)
	        	{
	        		if(set.count(s.substr(i,j-i)))//右边也存在
	        			dp[j] = true;
	        	}
        }
        return dp[n];
    }
};

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