Share my 8ms c++ solution

• I took advantage of the result from the problem 'word break', saving a dp table to help avoid repeating searches.

``````class Solution
{
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict)
{
/******** Below is the result form word break **********/
vector<bool> dp(s.size() + 1, false);
dp[0] = true;

for (int i = 1; i <= s.size(); ++i)
for (int j = i - 1; j >= 0 && !dp[i]; --j)
dp[i] = dp[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end();
if(!dp[s.size()]) return {};
/******************************************************/
vector<string> ret;
wordBreak(s, 0, wordDict, dp, "", ret);
return ret;
}

void wordBreak(const string &s, int beg, unordered_set<string> &wordDict, vector<bool> &dp, string str, vector<string> &ret)
{
if(beg == s.size())
{
ret.push_back(str.substr(0, str.size() - 1));  //eliminate the last space
return;
}

for(int i = beg + 1; i <= s.size(); ++i)
//We only go further for certain cases
if(dp[i] && wordDict.find(s.substr(beg, i - beg)) != wordDict.end())
wordBreak(s, i, wordDict, dp, str + s.substr(beg, i - beg) + " ", ret);
}
};``````

• 好棒啊..最后是用了一个回溯法么？？？？？？？？？？？？？？？？？？？

• 第一步是一个动态规划，你可以先看看word break I，第二步是回溯法

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.