140. Word Break II
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: []
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 33 34 35 | class Solution { public: vector<string> wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wdset(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n+1, false); dp[0] = true; for(int i=1; i<=n; ++i){ for(int j=i; j>0; --j){ string ss = s.substr(j-1, i-j+1); if(wdset.count(ss) && dp[j-1]){ dp[i] = true; break; } } } vector<string> ret; if(!dp[n]) return ret; bt(n-1, n, s, wdset, "", ret, dp); return ret; } void bt(int pos, int n, string s, unordered_set<string>& wordDict, string cur, vector<string> &ret, vector<bool> &dp){ if(pos==-1){ if(!cur.empty()) ret.push_back(cur); }else{ if(!cur.empty()) cur = " "+cur; for(int i = pos; i>=0; --i){ string ss = s.substr(i, pos-i+1); if(wordDict.count(ss) && dp[i]){ bt(i-1, n, s, wordDict, ss+cur, ret, dp); } } } } }; |
类似幺散久或者幺肆铃. 给定一由调换顺序之后的单词合并成的没有空格的字符串. 例如string = "iovleoyu", 然后给定一个字典数组dict = ['i', 'love', 'you'], 需要从字典里找出匹配的单词, 并打印正确的句子. "i love you".
开始没有思路, 想用Trie或者prefix hash发现是乱序的. 面试官提醒我可以排序生成hash, 我瞬间有了思路. 最后我给出的解决方案是, 用字典生成一个hash表, key是字母排序之后的单词, 然后对string使用动态规划进行查找. dp= dp || dp[j] && map[s[j...i].sort]. 最后找到dp为true的节点并生成句子.
4. Given morse code of each letter, and a list of words. Group words such that words in same group have same morse code.
Follow up: Given a morse code string and a dictionary of words. Break the morse code string such that each piece is valid word.
No comments:
Post a Comment