這道題用動態規劃解決。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet;for(string& word:wordDict){wordSet.insert(word);}int s_len = s.size();//s的下標從1開始起算，dp[j]表示s[1,j]能拆分成wordDict的組合vector<bool> dp(s_len+1,false);dp[0] = true;//表示空串for(int len = 1;len <= s_len;len++){//對s[1,len]遍歷for(int i = 0;i < len;i++){//對s[1,len]的拆分點遍歷if(dp[i] && wordSet.find(s.substr(i,len-i)) != wordSet.end()){dp[len] = true;break;}}}return dp[s_len];}
};

可以事先確定，wordDict中最長的單詞的長度max_word_len。這樣在考慮s.sub(i,len-i)時候，如果len-i大于max_word_len就可以直接跳過這種情況。

優化后的代碼：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet;int max_word_len = 0;for(string& word:wordDict){wordSet.insert(word);if(word.size() > max_word_len) max_word_len = word.size();}int s_len = s.size();//s的下標從1開始起算，dp[j]表示s[1,j]能拆分成wordDict的組合vector<bool> dp(s_len+1,false);dp[0] = true;//表示空串for(int len = 1;len <= s_len;len++){//對s[1,len]遍歷for(int i = 0;i < len;i++){//對s[1,len]的拆分點遍歷if(len -i > max_word_len)continue;if(dp[i] && wordSet.find(s.substr(i,len-i)) != wordSet.end()){dp[len] = true;break;}}}return dp[s_len];}
};