Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
private:
int minLen = INT_MAX, maxLen = INT_MIN;
int len_s = 0;
public:
void buildPath(string &s, vector<string> &res, string cur, unordered_set<string> &dict, vector<int>& isBreakable, int pos){
//We use minLen and maxLen to shrink the searching range
for(int i = minLen; i <= min(maxLen, len_s - pos); i++){
if(isBreakable[i + pos]==1 && dict.count(s.substr(pos, i))!=0){
if(i + pos == len_s) res.push_back(cur + s.substr(pos, i));
else buildPath(s, res, cur + s.substr(pos, i) + " ", dict, isBreakable, i+pos);
}
}
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<string> res;
if(wordDict.empty()) return res;
unordered_set<string> dict(wordDict.begin(), wordDict.end());
len_s = s.size();
vector<int> isBreakable(len_s+1, 0);
//Cut from the last of the string, which is comparing empty string, always be 1
isBreakable[len_s] = 1;
//Note the word.size() returns an usigned int
for(string word: wordDict){
minLen = minLen > static_cast<int>(word.size()) ? word.size() : minLen;
maxLen = maxLen < static_cast<int>(word.size()) ? word.size() : maxLen;
}
for(int i = len_s - minLen; i >= 0; i--){
for(int j = minLen; j <= min(maxLen, len_s - i); j++){
if(isBreakable[j+ i] == 1 && dict.count(s.substr(i, j))!=0){
isBreakable[i] = 1;
break;
}
}
}
if(isBreakable[0])
buildPath(s, res, "", dict, isBreakable, 0);
return res;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment