# word-break-ii（单词切分2）

<center>知识点：动态规划</center>


## 题目描述
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

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"].

-----

给定字符串s和单词字典dict，在s中添加空格以构造一个句子，其中每个单词都是有效的字典单词。

返回所有这些可能的句子。

比如：
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].

应该返回["cats and dog", "cat sand dog"].

## 解题思路

我们从某一个位置`index`将`s`切分为前后两个部分，分别记为`s1`和`s2`，如果`s1`在`dict`中，我们去计算`s2`计算的结果，然后将`s2`切分的结果与`s1`合并即可，如果`s2`不能切割，我们就从`index+1`继续对`s`进行切割，实际是一种`dfs`的思想，核心思想如下：

```java
ArrayList<String> wordBreak(String s, Set<String> dict){
	ArrayList<String> res;
  for(int index=1;index<s.length;index++){
    if(dict.contains(s[0:index])){
      ArrayList<String> list=wordBreak(s[index:],dict);
      if(list==null){
        continue;
      }else{
        res+=merge(s[0:index],list);
      }
    }
  }
  return res;
}
```

这样虽然可以解决问题，但是有点小瑕疵，考虑：`s="abcdefg"`,`dict={"bc","def","g"}`,那么：

- index=1 s1=a s2=bcdefg ,切割bcdefg
- Index=2 s1=ab s2=cdefg,切割cdefg
- index=3 s1=abc s2=defg，切割defg
- ...

注意，第一步切割`bcdefg`的时候递归调用了`wordBreak`，在切割`bcdefg`的时候也会切割`cdefg`、`defg`、`efg`、`fg`、`g`，然后下面几步也是类似的操作，所以说下面几步实际上做了一部分重复的工作，为了避免这种重复的工作，我们可以使用`Map`，将`s`与其切分的结果存下来，这样下次再遇到`s`的时候直接从`map`中取之前分好的结果就行了，不用做重复操作。


## 代码

[这里](../src/twelve/Solution.java)