[leetcode] 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"`.

First, I tried backtracking algorithm, but I met Time Limit Exceeded error.

Backtracking:o(n!)

```//can I reuse the words in dict?
//What should I return if s is an empty string?
//s = abc wordDict = "abc" ? what should I return?

class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
//extreme case
if(s.size() == 0 || wordDict.empty() == true) return false;
return _wordBreak(s, wordDict);

}
bool _wordBreak(string s, unordered_set<string>& wordDict){
//base condition
if(s.size() == 0) return true;

//ordinary case
for(size_t i = 0; i < s.size(); i++){
if(wordDict.find(s.substr(0, i + 1)) != wordDict.end()){
//s.substr is found in dict
if(_wordBreak(s.substr(i + 1, -1), wordDict) == true){
return true;
}
}
}
return false;
}
};```

Dynamic programming: o(n^2)

dp[i] = dp[j – 1] && s.substr(j, i – j + 1), 0 <= j <= i

```//can I reuse the words in dict?
//What should I return if s is an empty string?
//s = abc wordDict = "abc" ? what should I return?
//the time complexity of backtracking algorithm is unbearable o(n!)

//Dynamic programmming solution
//o(n^2)
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
//extreme case
if(s.size() == 0 || wordDict.empty() == true) return false;
bool dp[s.size()];
memset(dp, false, sizeof(dp));
for(size_t i = 0; i < s.size(); i++){
for(int j = i; j >= 0; j--){
if(wordDict.find(s.substr(j, i - j + 1)) != wordDict.end()){
if(j == 0) dp[i] = true;
else if(dp[j - 1] == true) dp[i] = true;

}
}

}
return dp[s.size() - 1];
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.