leetcode 139. Word Break

这道题用动态规划解决。

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];}
};