单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例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

该问题采用动态规划解法。考虑将原问题拆解为两个子问题，以"leetcode"为例，原问题为s，拆分成的两个子问题为"leet"，为"code"，如果和都有解，那么原问题s也有解，s还可以拆分成"lee"和"tcode"，在拆分成的这么多子问题中，只要任意一组子问题有解，那么s就有解。

直接采用暴力拆解会重复计算很多子问题，如计算"lee"和"leet"的子问题。因此采用动态规划避免重复求解子问题。求解时，先初始化长度为s.length()+1的dp数组，当字符串为空时，默认为有解，因此dp[0]为true，其它的都先初始化为false。假设当前求解的字符串长度为i，字符串的分割点为j，即字符串被分成s(0,j)和s(j+1,i)两个部分，s(0,j)即为dp[j]，在之前的结果中可以直接取到，因此只需要再求wordDict中是否包含s(j+1,i)。当dp[j]为true并且wordDict包含s(j+1,i)时，dp[i]为true。从这个计算过程也可以明显看出，在求解过程中省去了重复计算子问题s(0,j)。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
       vector<bool> dp;
        dp.push_back(true);
        for(int i=1;i<=s.size();i++) dp.push_back(false);
        for(int i=1;i<=s.size();i++){
            for(int j=0;j<i;j++){
                auto match = find(wordDict.begin(),wordDict.end(),s.substr(j,i-j));
                if(match != wordDict.end() && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};