140 Word Break II

140. Word Break II​
1. Question
Given a non-empty strings 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. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given
s="catsanddog",
dict=["cat", "cats", "and", "sand", "dog"].
A solution is["cats and dog", "cat sand dog"].
2. Implementation
(1) DFS + Memoization
1
class Solution {
2
    public List<String> wordBreak(String s, List<String> wordDict) {
3
        Set<String> dict = new HashSet(wordDict);
4
        Map<Integer, List<String>> cache = new HashMap();
5
​
6
        return breakWord(s, 0, dict, cache);
7
    }
8
​
9
    public List<String> breakWord(String s, int start, Set<String> dict, Map<Integer, List<String>> cache) {
10
        List<String> res = new ArrayList();
11
​
12
        if (start == s.length()) {
13
            res.add("");
14
            return res;
15
        }
16
​
17
        for (int i = start + 1; i <= s.length(); i++) {
18
            if (dict.contains(s.substring(start, i))) {
19
                List<String> list = new ArrayList();
20
​
21
                if (cache.containsKey(i)) {
22
                    list = cache.get(i);
23
                }
24
                else {
25
                    list = breakWord(s, i, dict, cache);
26
                }
27
​
28
                for (String str : list) {
29
                    res.add(s.substring(start, i) + (str.length() == 0 ? "" : " ") + str);
30
                }
31
            }
32
        }
33
        cache.put(start, res);
34
        return res;
35
    }
36
}
Copied!
3. Time & Space Complexity
时间复杂度O(2^n), 考虑字典[a, aa, aaa, aaaa, aaaaa], input = "aaaaa....", 总共有2^n个解
空间复杂度O(mn), m是dict的word个数，n是input string的长度

139 Word Break

152 Maximum Product Subarray

Last modified 2yr ago

Copy link

Contents

140. Word Break II

1. Question

2. Implementation

3. Time & Space Complexity

140. Word Break II​

1. Question

2. Implementation

3. Time & Space Complexity

140. Word Break II