Thursday, April 9, 2015

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]. 最后找到dptrue的节点并生成句子.


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.

No comments:

Post a Comment