Word Break

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = “leetcode”,
dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

Follow-up: return all the possible combinations of words.

test

Solution

Explanation will be added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
int size = s.length();
int isBreakable[size+1]{0};
int wMinLen = INT_MAX, wMaxLen = INT_MIN;
for(auto& w: wordDict) {
wMinLen = min(wMinLen, (int)w.length());
wMaxLen = max(wMaxLen, (int)w.length());
}
isBreakable[0] = 1;
for(int i = wMinLen; i <= size; ++i) {
for(int l = wMinLen; l <= min(wMaxLen, i); ++l)
if(isBreakable[i-l] && wordDict.count(s.substr(i-l, l)))
isBreakable[i] = 1;
}
return isBreakable[size];
}
};

Follow-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private:
int sLen, wMinLen, wMaxLen;
void search(string& s, int pos, bool isBreakable[], string path, vector<string>& v, unordered_set<string>& wordDict) {
for(int len = wMinLen; len <= min(wMaxLen, sLen-pos); ++len) {
string t = s.substr(pos, len);
if(isBreakable[pos+len] && wordDict.count(t)) {
if(pos+len == sLen) v.push_back(path+t);
else search(s, pos+len, isBreakable, path+t+" ", v, wordDict);
}
}
}
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
sLen = s.length();
wMinLen = INT_MAX, wMaxLen = INT_MIN;
for(auto& w: wordDict) {
wMinLen = min(wMinLen, (int)w.length());
wMaxLen = max(wMaxLen, (int)w.length());
}
bool isBreakable[sLen+1]{false};
isBreakable[0] = 1;
for(int i = wMinLen; i <= sLen; ++i) {
for(int l = wMinLen; l <= min(wMaxLen, i); ++l)
if(isBreakable[i-l] && wordDict.count(s.substr(i-l, l)))
isBreakable[i] = 1;
}
vector<string> v;
if(isBreakable[sLen]) search(s, 0, isBreakable, "", v, wordDict);
return v;
}
};

Always welcome new ideas and practical tricks, just leave them in the comments!