采用动态规划算法
// write code here
vector<vector<string>> dp(s.length()+1, vector<string>());
set<string> wordDict;
for(auto d : dic){
wordDict.insert(d);
}
int len = s.length();
dp[0] = {""};
for (int i = 1; i <= len; i++) {
for (int j = i - 1; j >= 0; j--) {
if (dp[j].size() == 0) continue;
string suffix = s.substr(j, i-j);
if (wordDict.find(suffix) != wordDict.end() && dp[j].size()) { //若发现从j->i这一段字符串存在于set中,并且dp[j]有句子,那么就可以对dp[j]中的每个句子新增这一字符串得到此处的dp[i]
for(auto d : dp[j]){
dp[i].push_back(d + (j == 0 ? "" : " ") + suffix);
}
}
}
}
sort(dp[s.length()].begin(), dp[s.length()].end());
return dp[s.length()];
}