单词切分2.md

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

知识点：动态规划

题目描述

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的思想，核心思想如下：

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中取之前分好的结果就行了，不用做重复操作。

代码

这里