题目描述（困难难度）

的升级版。给一个字符串，和一些单词，找出由这些单词组成该字符串的所有可能，每个单词可以用多次，也可以不用。

完全按照 139 题 的思路做了，大家可以先过去看一下。

解法一 动态规划

先考虑 最后一个解法，动态规划，看起来也比较简单粗暴。

这里修改的话，我们只需要用 dp[i] 表示字符串 s[0,i) 由 wordDict 构成的所有情况。

总体思想还是和之前一样的。

  1. X X X X X X
  2. ^     ^   ^
  3. 0     j   i
  4. 先判断 j 到 i 的字符串在没在 wordDict 中
  5. 然后把 0 到 j 的字符串由 wordDict 构成所有情况后边加空格再加上 j 到 i 的字符串即可

遗憾的是，熟悉的问题又来了。

由于 s 中的 b 字母在 wordDict 中并没有出现，所以其实我们并不需要做那么多循环，直接返回空列表即可。

和之前一样，所以我们可以先遍历一遍 s 和 wordDict ，从而确定 s 中的字符是否在 wordDict 中存在，如果不存在可以提前返回空列表。

  1. public List<String> wordBreak(String s, List<String> wordDict) {
  2.     //提前进行一次判断
  3.     HashSet<Character> set2 = new HashSet<>();
  4.     for (int i = 0; i < wordDict.size(); i++) {
  5.         String t = wordDict.get(i);
  6.         for (int j = 0; j < t.length(); j++) {
  7.             set2.add(t.charAt(j));
  8.         }
  9.     }
  10.     for (int i = 0; i < s.length(); i++) {
  11.         if (!set2.contains(s.charAt(i))) {
  12.             return new ArrayList<>();
  13.         }
  14.     }
  16.     HashSet<String> set = new HashSet<>();
  18.         set.add(wordDict.get(i));
  19.     }
  20.     List<List<String>> dp = new ArrayList<>();
  21.     temp.add("");
  22.     dp.add(temp);
  23.     for (int i = 1; i <= s.length(); i++) {
  24.         temp = new ArrayList<>();
  25.         for (int j = 0; j < i; j++) {
  26.             if (set.contains(s.substring(j, i))) {
  27.                 for (int k = 0; k < dp.get(j).size(); k++) {
  28.                     String t = dp.get(j).get(k);
  29.                     if (t.equals("")) {
  30.                         temp.add(s.substring(j, i));
  31.                     } else {
  32.                         temp.add(t + " " + s.substring(j, i));
  33.                     }
  35.                 }
  37.             }
  38.         }
  39.         dp.add(temp);
  40.     }
  41.     return dp.get(s.length());
  42. }

遗憾的是，刚刚那个例子通过了，又出现了新的问题。

140. Word Break II - 图3

再优化也想不到方法了，是我们的算法出问题了。因为 139 题中找到一个解以后就 break 了，而这里我们要考虑所有子串，所有的解，极端情况下时间复杂度达到了 O(n³)。还有一点致命的是，我们之前求的解最后可能并不需要。举个例子。

针对这个问题，我们可以优化一下，也就是下边的解法二

解法二

我们直接用递归的方法，先判断当前字符串在不在 wordDict 中，如果在的话就递归的去求剩余字符串的所有组成可能。此外，吸取之前的教训，直接使用 memoization 技术，将递归过程中求出来的解缓存起来，便于之后直接用。

  2.     HashSet<String> set = new HashSet<>();
  3.     for (int i = 0; i < wordDict.size(); i++) {
  4.         set.add(wordDict.get(i));
  5.     }
  6.     return wordBreakHelper(s, set, new HashMap<String, List<String>>());
  8. private List<String> wordBreakHelper(String s, HashSet<String> set, HashMap<String, List<String>> map) {
  9.     if (s.length() == 0) {
  10.         return new ArrayList<>();
  11.     }
  12.     if (map.containsKey(s)) {
  13.         return map.get(s);
  14.     }
  15.     List<String> res = new ArrayList<>();
  16.     for (int j = 0; j < s.length(); j++) {
  17.         //判断当前字符串是否存在
  18.         if (set.contains(s.substring(j, s.length()))) {
  19.             //空串的情况，直接加入
  20.             if (j == 0) {
  21.                 res.add(s.substring(j, s.length()));
  22.             } else {
  23.                 //递归得到剩余字符串的所有组成可能，然后和当前字符串分别用空格连起来加到结果中
  24.                 List<String> temp = wordBreakHelper(s.substring(0, j), set, map);
  25.                 for (int k = 0; k < temp.size(); k++) {
  26.                     String t = temp.get(k);
  27.                     res.add(t + " " + s.substring(j, s.length()));
  28.                 }
  29.             }
  31.         }
  32.     }
  33.     //缓存结果
  34.     map.put(s, res);
  35. }

总

按理说其实可以直接就想到解法二，但受之前写的题的影响，这种分治的问题，都最终能转成动态规划，所以先写了动态规划的思路，想直接一步到位，没想到反而遇到了问题，很有意思，哈哈。原因就是你求子问题的代价很大，而动态规划就是要求所有的子问题。而解决最终问题的时候，一些子问题其实是没有必要的。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情