LintCode 582: Word Break II

582. Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

Example
Example 1:

Input：“lintcode”，[“de”,“ding”,“co”,“code”,“lint”]
Output：[“lint code”, “lint co de”]
Explanation：
insert a space is “lint code”，insert two spaces is “lint co de”.
Example 2:

Input：“a”，[]
Output：[]
Explanation：dict is null.

解法1：DFS+Memorization
把s按pos=1,2,…,len-1切成2半，如果前半部subStr1在dict里面， 那么后半部subStr2就可以按子问题处理。
注意要Memorization，不然过不了下面的input case:
“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”
[“a”,“aa”,“aaa”,“aaaa”,“aaaaa”,“aaaaaa”,“aaaaaaa”,“aaaaaaaa”,“aaaaaaaaa”,“aaaaaaaaaa”]

代码如下：

class Solution {
public:/** @param s: A string* @param wordDict: A set of words.* @return: All possible sentences.*/vector<string> wordBreak(string &s, unordered_set<string> &wordDict) {map<string, vector<string>> memo;return helper(s, wordDict, memo);}private:vector<string> helper(string &s, unordered_set<string> &wordDict, map<string, vector<string>> &memo) {int len = s.size();if (len == 0) return {};if (memo.find(s) != memo.end()) return memo[s];vector<string> result;for (int i = 1; i <= len; ++i) {string subStr1 = s.substr(0, i);if (wordDict.find(subStr1) != wordDict.end()) {if (subStr1.size() == len) {result.push_back(subStr1);   } else {string subStr2 = s.substr(i);vector<string> tmpRes;tmpRes = helper(subStr2, wordDict, memo);//tmpRes = helper(subStr2, wordDict);for (auto t : tmpRes) {result.push_back(subStr1 + " " + t);}}}}memo[s] = result;return result;}
};

代码同步在
https://github.com/luqian2017/Algorithm

二刷：还是调了很久才调通，

class Solution {
public:/*** @param s: A string* @param wordDict: A set of words.* @return: All possible sentences.*          we will sort your return value in output*/vector<string> wordBreak(string &s, unordered_set<string> &wordDict) {for (auto w : wordDict) {minLen = min(minLen, (int)w.size());maxLen = max(maxLen, (int)w.size());}if (maxLen == 0) return {};string sol = "";vector<string> sols;unordered_map<int, vector<string>> um_str;unordered_map<int, int> um_res; //0: uninitialized, 1: true, -1: false;um_str[0] = {};helper(s, wordDict, um_str, um_res, s.size(), sol);return um_str[s.size()];}
private:int minLen = INT_MAX, maxLen = INT_MIN;void helper(string &s, unordered_set<string> &wordDict, unordered_map<int, vector<string>> &um_str, unordered_map<int, int> &um_res, int pos, string sol) {int upperLimit = min(maxLen, pos);//   0---------------pos------len//           <---i----//   is [pos - i, i] an exisiting string in wordDict?for (int i = minLen; i <= upperLimit; i++) {if (um_res[pos - i] < 0) continue;string str = s.substr(pos - i, i);if (wordDict.find(str) == wordDict.end()) continue;if (um_res[pos - i] == 0) helper(s, wordDict, um_str, um_res, pos - i, sol);if (pos == i || um_res[pos - i] > 0) {if (um_str[pos - i].size() > 0) {for (auto s : um_str[pos - i]) {um_str[pos].push_back(s + " " + str);}} else {um_str[pos].push_back(str);}um_res[pos] = 1;//return true;  //注意这里不能返回，不然得到一个解就结束了。} else if (um_res[pos] == 0) { //注意这里要检查um_res[pos]是否有过可行解，不然这次如果没有解，会把以前的可行解删掉。um_res[pos] = -1;um_str[pos] = {};}}return;}};

解法3：跟解法2差不多，不过解法2的pos是从尾扫到头，这里pos是从头扫到尾。

class Solution {
public:/*** @param s: A string* @param wordDict: A set of words.* @return: All possible sentences.*          we will sort your return value in output*/vector<string> wordBreak(string &s, unordered_set<string> &wordDict) {for (auto w : wordDict) {minLen = min(minLen, (int)w.size());maxLen = max(maxLen, (int)w.size());}if (maxLen == 0) return {};string sol = "";vector<string> sols;unordered_map<int, vector<string>> um_str;unordered_map<int, bool> um_res; //int len = s.size();um_str[len] = {};helper(s, wordDict, um_str, um_res, 0, sol);return um_str[0];}
private:int minLen = INT_MAX, maxLen = INT_MIN;void helper(string &s, unordered_set<string> &wordDict, unordered_map<int, vector<string>> &um_str, unordered_map<int, bool> &um_res, int pos, string sol) {//int upperLimit = min(maxLen, pos);//   0----->--pos------------len//              ---i---->//   is [pos, pos + i] an exisiting string in wordDict?int len = s.size();for (int i = minLen; i <= maxLen && pos + i <= len; i++) {if (um_res.find(pos + i) != um_res.end() && um_res[pos + i] == false) continue;string str = s.substr(pos, i);if (wordDict.find(str) == wordDict.end()) continue;if (um_res.find(pos + i) == um_res.end()) helper(s, wordDict, um_str, um_res, pos + i, sol);if (pos + i == len || um_res[pos + i]) {if (um_str[pos + i].size() > 0) {for (auto s : um_str[pos + i]) {um_str[pos].push_back(str + " " + s);}} else {//if (pos + i == len) {um_str[pos].push_back(str);}um_res[pos] = true;} else if (um_res.find(pos) == um_res.end()) {um_res[pos] = false;um_str[pos] = {};}}return;}};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！