leetcode 140:单词拆分 II

使用首先使用139的动态规划来判断是否可以进行切分，之后进行回溯法进行切分

bool wordBreak1(std::string s, std::vector<std::string>& wordDict) {
    std::vector<int> dp(s.size()+1);
    dp[0]=1;
    for(int i=0;i<s.size()+1;i++){
        for(int j=0;j<=i;j++){
            if(dp[j]&&std::find(wordDict.begin(),wordDict.end(),s.substr(j,i-j))!=wordDict.end()){
                dp[i]=1;
            }
        }
    }
    return dp[s.size()];
}

void breakWo(std::string s,std::vector<std::string>& wordDict,std::vector<std::string> &ss,std::string &s1){
    if(s.size()==0)
    {
        s1=s1.substr(0,s1.size()-1);
        ss.push_back(s1);
    }
    else
    {   std::string s2=s1;
        for(int i=0;i<s.size();i++){
            s1=s2;
            if(std::find(wordDict.begin(),wordDict.end(),s.substr(0,i+1))!=wordDict.end()){
                s1+=s.substr(0,i+1)+" ";
                breakWo(s.substr(i+1),wordDict,ss,s1);
            }
        }
    }

}

std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
    std::vector<std::string> ss;
    std::string s1="";
    if(!wordBreak1(s,wordDict))
        return ss;
    else
        breakWo(s,wordDict,ss,s1);
    return ss;
}