LeetCode [140] Word Break II

 140. Word Break II

Hard

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:
[]

Accepted

283,760

Submissions

840,259

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); } } } } };

YMSF

类似幺散久或者幺肆铃. 给定一由调换顺序之后的单词合并成的没有空格的字符串. 例如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的节点并生成句子.

YMSF

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.