Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
if(wordDict.empty()) return false;
int len_s = s.size();
vector<int> dp(len_s + 1, 0);
dp[len_s] = 1;
unordered_set<string> dict(wordDict.begin(), wordDict.end());
for(int i = len_s - 1; i>=0; i--){
string tempS = "";
for(int j = i; j < len_s; j++){
tempS += s[j];
dp[i] = dict.count(tempS);
// dp[i] here means whether substring[i, j] can be segmented
//When the inner loop is over, dp[i] means whether substring[i, end] can be segmented
if(dp[i]!=0 && dp[j+1] !=0)
break;
}
}
return dp[0];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment