# 0140. Word Break II

<https://leetcode.com/problems/word-break-ii>

## Description

Given a string `s` and a dictionary of strings `wordDict`, add spaces in `s` to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in **any order**.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

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

**Constraints:**

* `1 <= s.length <= 20`
* `1 <= wordDict.length <= 1000`
* `1 <= wordDict[i].length <= 10`
* `s` and `wordDict[i]` consist of only lowercase English letters.
* All the strings of `wordDict` are **unique**.

## ac1: DFS with memorization

Complexity: worst case is O(2^n), e.g. `input "aaaaaa", with wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaa"].` Every possible partition is a valid sentence, and there are 2^n-1 such partitions.

With cache, the runtime improves from O(2^n) to O(n^2), e.g. `"aaaaab", with wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaa"]`. Why O(n^2)? Think reversely, it's just like finding valid partitions like O(n^2) DP in [0139. Word Break](https://jaywin.gitbook.io/leetcode/solutions/0139-word-break).

```java
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        // edge cases
        if (s == null || wordDict == null || s.length() == 0 || wordDict.size() == 0) 
            return new ArrayList<String>();

        Set<String> dict = new HashSet<String>(wordDict);
        Map<Integer,List<String>> map = new HashMap<Integer,List<String>>();
        return dfs(s, 0, dict, map);
    }

    private List<String> dfs(String s, int start, Set<String> dict, Map<Integer,List<String>> map) {
        List<String> res = new ArrayList<String>();
        // exit
        if (start == s.length()) res.add(""); // reach the end, validate string

        // check map, avoid repeated work
        if (map.containsKey(start)) return map.get(start);

        // process
        for (int e = start + 1; e <= s.length(); e++) {
            String w = s.substring(start, e);
            if (dict.contains(w)) {
                List<String> next = dfs(s, e, dict, map);
                for (String str : next) {
                    res.add(w + (str.equals("") ? "" : " ") + str);
                }
            }
        }
        map.put(start, res);

        return res;
    }
}

/*
DFS, memorization

iterate characters, if in dict, dfs check remaining:
    if substring is validate, it returns word list, append all
    else return empty list
*/
```