Given a non-empty string s and a dictionary wordDictcontaining a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "catsanddog" wordDict =["cat", "cats", "and", "sand", "dog"]Output:[ "cats and dog", "cat sand dog" ]
Example 2:
Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.
============ Recursive (Time limit exceed) ==========
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<string> sol;
string ans;
set<string> st(wordDict.begin(), wordDict.end());
//helper(s, 0, ans, st, sol);
sol = helperDynamic(s, st);
return sol;
}
void helper(string s, int idx, string ans, set<string>& st,
vector<string>& sol) {
if (idx == s.size()) {
sol.push_back(ans);
return;
}
for (int i = idx; i < s.size(); i++) {
string subStr = s.substr(idx, i - idx + 1);
string strAns = ans;
if (st.count(subStr)) {
if (ans.empty()) {
ans = subStr;
} else {
ans += " ";
ans += subStr;
}
helper(s, i + 1, ans, st, sol);
ans = strAns;
}
}
return;
}
};
============= Dynamic (Time limit exceed too) ============
vector<string> append(vector<string> input, string s) {vector<string> ans;
if (s.size() == 0) {
return input;
}
for (auto str : input) {
string newStr = str + " " + s;
ans.push_back(newStr);
}
if (ans.size() == 0) {
ans.push_back(s);
}
return ans;
}
vector<string> helperDynamic(string s, set<string>& st) {
vector<string> ans;
map<string, vector<string>> mp;
for (int i = 0; i < s.size(); i++) {
for (int j = i; j >= 0; j--) {
string rightStr = s.substr(j, i - j + 1);
if (!st.count(rightStr)) {
continue;
}
if (j == 0) {
mp[rightStr].push_back(rightStr);
continue;
}
string leftStr = s.substr(0, j);
if (!mp.count(leftStr)) {
continue;
}
// Append new answer to the earlier computed one.
vector<string> newAns = append(mp[leftStr], rightStr);
// Insert newAns into the existing solution.
mp[leftStr + rightStr].insert(mp[leftStr + rightStr].end(),
newAns.begin(), newAns.end());
}
}
return (mp.count(s) != 0 ? mp[s] : ans);
}
============== Dynamic (Memory limit exceed) ========
class Solution {
private:
unordered_map<string, vector<string>> mp;
vector<string> append(const vector<string>& input, const string& s) {
vector<string> ans;
if (s.size() == 0) {
return ans;
}
for (const auto& str : input) {
ans.push_back(str + " " + s);
}
return ans;
}
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> st(wordDict.begin(), wordDict.end());
return helperDynamic(s, st);
}
const vector<string>& helperDynamic(string s, unordered_set<string>& st) {
for (int i = 0; i < s.size(); i++) {
const string& partialStr = s.substr(0, i + 1);
if (mp.count(partialStr)) {
continue;
}
vector<string> ans;
if (st.count(partialStr)) {
ans.push_back(partialStr);
}
for (int j = i; j >= 0; j--) {
const string& rightStr = s.substr(j, i - j + 1);
if (!st.count(rightStr)) {
continue;
}
const string& leftStr = s.substr(0, j);
// Append new answer to the earlier computed one.
const vector<string>& newAns = append(mp[leftStr], rightStr);
// Insert newAns into the existing solution.
ans.insert(ans.end(), newAns.begin(), newAns.end());
}
mp[partialStr].swap(ans);
}
return mp[s];
}
};
============== Recursive with memorization working solution =====
https://zxi.mytechroad.com/blog/leetcode/leetcode-140-word-break-ii/
=============== Beautiful recursion with memorization ==========
https://www.cnblogs.com/grandyang/p/4576240.html
================= Again ===========
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<string> sol;
string ans;
unordered_set st(wordDict.begin(), wordDict.end());
// recursive
//helper(s, 0, st, ans, sol);
//return sol;
// Memoization..
unordered_map<int, vector<string>> mp;
return dp_helper(s, 0, st, mp);
}
vector<string> dp_helper(string s, int idx,
unordered_set<string>& st,
unordered_map<int, vector<string>> mp) {
if (mp.count(idx) != 0) {
return mp[idx];
}
vector<string> ans;
for (int i = idx; i < s.size(); i++) {
string str = s.substr(idx, i - idx + 1);
if (st.count(str) != 0) {
vector<string> remaining = dp_helper(s, i + 1, st, mp);
if (remaining.size() == 0 && i != s.size() - 1) {
continue;
}
remaining = append_str(remaining, str);
ans.insert(ans.end(), remaining.begin(), remaining.end());
}
}
mp[idx] = ans;
return mp[idx];
}
vector<string> append_str(vector<string>& input, string str) {
vector<string> results;
if (input.size() == 0) {
results.push_back(str);
return results;
}
for (auto& inp_str : input) {
results.push_back(str + " " + inp_str);
}
return results;
}
void helper(string s, int idx, unordered_set<string>& st, string ans,
vector<string>& sol) {
if (idx == s.size() && ans.size() != 0) {
sol.push_back(ans);
return;
}
for (int i = idx; i < s.size(); i++) {
string str = s.substr(idx, i - idx + 1);
if (st.count(str) != 0) {
string tmp = ans;
if (ans.size() != 0) {
ans += " " + str;
} else {
ans = str;
}
helper(s, i + 1, st, ans, sol);
ans = tmp;
}
}
}
};
No comments:
Post a Comment