# 140     Word Break II

## 140. [Word Break II](https://leetcode.com/problems/word-break-ii/description/)

## 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**

```java
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet(wordDict);
        Map<Integer, List<String>> cache = new HashMap();

        return breakWord(s, 0, dict, cache);
    }

    public List<String> breakWord(String s, int start, Set<String> dict, Map<Integer, List<String>> cache) {
        List<String> res = new ArrayList();

        if (start == s.length()) {
            res.add("");
            return res;
        }

        for (int i = start + 1; i <= s.length(); i++) {
            if (dict.contains(s.substring(start, i))) {
                List<String> list = new ArrayList();

                if (cache.containsKey(i)) {
                    list = cache.get(i);
                }
                else {
                    list = breakWord(s, i, dict, cache);
                }

                for (String str : list) {
                    res.add(s.substring(start, i) + (str.length() == 0 ? "" : " ") + str);
                }
            }
        }
        cache.put(start, res);
        return res;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(2^n), 考虑字典\[a, aa, aaa, aaaa, aaaaa], input = "aaaaa....", 总共有2^n个解

空间复杂度O(mn), m是dict的word个数，n是input string的长度
