Given a non-empty string s and a dictionary wordDict containing 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.
Example 3:
Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []
A:
----------------就是简单的 DP-------------
class Solution { public: vector<string> wordBreak(string s, vector<string>& wordDict) { unordered_set<string> S(wordDict.begin(), wordDict.end()); int maxWordLen = 0; for (auto s : wordDict) { maxWordLen = max(maxWordLen, (int)s.length()); } unordered_map<int, vector<string>> map; for(int end =0; end<s.length(); end++){ for(int start = max(0,end-maxWordLen+1); start<=end;start++){ string curStr = s.substr(start, end-start+1); if(S.find(curStr) != S.end()){ // find current substring if(start == 0){ map[end].push_back(curStr); }else if(map[start-1].size()>0){ for(auto s:map[start-1]) map[end].push_back(s +" "+curStr); } } } } return map[s.length()-1]; } };
然而LTE了。进一步的改进是减少中间的存储内容。每次,只是保存前面substring的index
这种分治的问题,都最终能转成动态规划,所以先写了动态规划的思路,想直接一步到位,没想到反而遇到了问题,很有意思,哈哈。原因就是你求子问题的代价很大,而动态规划就是要求所有的子问题。而解决最终问题的时候,一些子问题其实是没有必要的。
class Solution { public: vector<string> wordBreak(string s, vector<string>& wordDict) { unordered_set<string> S(wordDict.begin(), wordDict.end()); int maxWordLen = 0; for (auto s : wordDict) maxWordLen = max(maxWordLen, (int)s.length()); unordered_map<int, vector<int>> map; for (int end = 0; end < s.length(); end++) { for (int start = max(0, end - maxWordLen + 1); start <= end; start++) { if (S.find(s.substr(start, end - start + 1)) != S.end() && (start == 0 || map[start - 1].size() > 0)) map[end].push_back(start - 1); } } return buildResult(s, s.length() - 1, map); } private: vector<string> buildResult(string s, int endIndex, unordered_map<int, vector<int>>& map) { vector<string> res; for (auto preEndIndex : map[endIndex]) { if (preEndIndex == -1) { res.push_back(s.substr(0, endIndex+1)); } else { vector<string> preRes = buildResult(s, preEndIndex, map); for (auto pre : preRes) res.push_back(pre + " " + s.substr(preEndIndex + 1, endIndex - preEndIndex)); } } return res; } };
****************************4th pass*************************************
Error :
1: one stupid problem is that, when writing the list[end].get(i) at line 25, I mistakenly write it as list[end].indexOf(i); which is really cost me an hour in Leetcode , damn it
2: for 100 days without coding, I even forget that the generic types should be clearly set in the the function declaration.
Like: in the buildList()
***************************************
public class Solution { public List<String> wordBreak(String s, Set<String> dict) { if(s == null || s.length()==0) return new LinkedList<String>(); List<List<Integer>> all = new LinkedList();// for every position for(int i =0;i<s.length();i++){ List<Integer> curList = new LinkedList(); for(int j =i;j>=0;j--){ if( dict.contains(s.substring(j,i+1)) && (j==0 || all.get(j-1).size()>0 )) curList.add(j); //j is the starting point } all.add(curList); } return bfs(all,s,s.length()-1 ); } private List<String> bfs( List<List<Integer>> all, String s, int end){ List<String> list = new LinkedList(); if(end < 0){ list.add(""); return list; } for( int i : all.get(end)){ List<String> pre = bfs(all,s,i-1); for(String str:pre) list.add( new String(str + " " + s.substring(i,end+1) ).trim()); } return list; } }
Error :
1: one stupid problem is that, when writing the list[end].get(i) at line 25, I mistakenly write it as list[end].indexOf(i); which is really cost me an hour in Leetcode , damn it
2: for 100 days without coding, I even forget that the generic types should be clearly set in the the function declaration.
Like: in the buildList()
***************************************
No comments:
Post a Comment