LeetCode 140. 单词拆分 II（DP+回溯）

示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int i, j, n = s.size();
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        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;
                }
        }
        if(dp[n] == true)//整个字符串可以拆
        {
            vector<string> ans;
            string str;
            int end = 1;
            while(end <= n && dp[end] != 1)
                end++;//找到下一个可拆点
            bt(s,set,dp,ans,str,0,end);
            return ans;
        }
        else
            return {};//不能拆，返回空
    }

    void bt(string &s, unordered_set<string> &set, bool *dp, vector<string> &ans,
            string str, int start, int end)
    {
        if(start >= end)
            return;
        string temp = s.substr(start,end-start);//[s,e]的字符
        bool inSet = set.count(temp);//该字符在set集合中
        if(end == s.size())//取到最后字符了
        {
            if(inSet)
                ans.push_back(str+temp);//将前缀和当前组合，加入答案
            return;
        }
        int next = end+1;
        while(next <= s.size() && dp[next] != 1)
            next++;//找下一个分割点
        bt(s,set,dp,ans,str,start,next);//不插入空格，start不变，end变下一个
        if(inSet)//字符在集合中，才能加空格
            bt(s,set,dp,ans,str+temp+" ",end,next);//start变end，end变next
    }
};