题目描述（中等难度）

给一个字符串，和一些单词，问字符串能不能由这些单词构成。每个单词可以用多次，也可以不用。

解法一 回溯

来一个简单粗暴的方法，利用回溯法，用 wordDict 去生成所有可能的字符串。期间如果出现了目标字符串 s，就返回 true。

public boolean wordBreak(String s, List<String> wordDict) { return wordBreakHelper(s,wordDict,""); } //temp 是当前生成的字符串 private boolean wordBreakHelper(String s, List<String> wordDict, String temp) { //如果此时生成的字符串长度够了，就判断和目标字符日是否相等 if(temp.length() == s.length()){ if(temp.equals(s)){ return true; }else{ return false; } } //长度超了，就返回 false if(temp.length() > s.length()){ return false; } //考虑每个单词 for(int i = 0;i < wordDict.size(); i++){ if(wordBreakHelper(s,wordDict,temp + wordDict.get(i))){ return true; } } return false; } 

意料之中，超时了

让我们考虑优化的方法。

在递归出口的地方优化一下。

之前是在长度相等的时候，开始判断字符串是否相等。

很明显，字符串长度相等之前我们其实就可以判断当前是不是符合了。

例如 temp = "abc"，如果 s = "dddefg"，虽然此时 temp 和 s 的长度不相等。但因为前缀已经不同，所以后边无论是什么都不可以了。此时就可以返回 false 了。

所以递归出口可以从头判断每个字符是否相等，不相等就直接返回 false。

for (int i = 0; i < temp.length(); i++) { if (s.charAt(i) != temp.charAt(i)) { return false; } } 

然后代码就是下边的样子。

public boolean wordBreak(String s, List<String> wordDict) { return wordBreakHelper(s, wordDict, ""); } private boolean wordBreakHelper(String s, List<String> wordDict, String temp) { if (temp.length() > s.length()) { return false; } //判断此时对应的字符是否全部相等 for (int i = 0; i < temp.length(); i++) { if (s.charAt(i) != temp.charAt(i)) { return false; } } if (s.length() == temp.length()) { return true; } for (int i = 0; i < wordDict.size(); i++) { if (wordBreakHelper(s, wordDict, temp + wordDict.get(i))) { return true; } } return false; } 

遗憾的是，依旧是超时

发现上边的例子答案很明显是 false，因为 s 中的 b 字母在 wordDict 中并没有出现。

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

所以代码可以继续优化。

public boolean wordBreak(String s, List<String> wordDict) { HashSet<Character> set = new HashSet<>(); //将 wordDict 的每个字母放到 set 中 for (int i = 0; i < wordDict.size(); i++) { String t = wordDict.get(i); for (int j = 0; j < t.length(); j++) { set.add(t.charAt(j)); } } //判断 s 的每个字母在 set 中是否存在 for (int i = 0; i < s.length(); i++) { if (!set.contains(s.charAt(i))) { return false; } } return wordBreakHelper(s, wordDict, ""); } private boolean wordBreakHelper(String s, List<String> wordDict, String temp) { if (temp.length() > s.length()) { return false; } for (int i = 0; i < temp.length(); i++) { if (s.charAt(i) != temp.charAt(i)) { return false; } } if (s.length() == temp.length()) { return true; } for (int i = 0; i < wordDict.size(); i++) { if (wordBreakHelper(s, wordDict, temp + wordDict.get(i))) { return true; } } return false; } 

令人悲伤的是

还有 5 个 test 没有通过。还有什么可以优化的地方呢？

是时候拿出绝招了，在前边的题已经用过很多很多次，memoization 技术。思想就是把回溯中已经考虑过的解存起来，第二次回溯过来的时候可以直接使用。

这里的话，我们可以用一个 HashMap，key 的话就存 temp，value 的话就代表以当前 temp 开始的字符串，经过后边的尝试是否能达到目标字符串 s。

public boolean wordBreak(String s, List<String> wordDict) { HashSet<Character> set = new HashSet<>(); for (int i = 0; i < wordDict.size(); i++) { String t = wordDict.get(i); for (int j = 0; j < t.length(); j++) { set.add(t.charAt(j)); } } for (int i = 0; i < s.length(); i++) { if (!set.contains(s.charAt(i))) { return false; } } return wordBreakHelper(s, wordDict, "", new HashMap<String,Boolean>()); } private boolean wordBreakHelper(String s, List<String> wordDict, String temp, HashMap<String, Boolean> hashMap) { if (temp.length() > s.length()) { return false; } //之前是否存过 if(hashMap.containsKey(temp)){ return hashMap.get(temp); } for (int i = 0; i < temp.length(); i++) { if (s.charAt(i) != temp.charAt(i)) { return false; } } if (s.length() == temp.length()) { return true; } for (int i = 0; i < wordDict.size(); i++) { if (wordBreakHelper(s, wordDict, temp + wordDict.get(i), hashMap)) { //结果放入 hashMap hashMap.put(temp, true); return true; } } //结果放入 hashMap hashMap.put(temp, false); return false; } 

这次就成功通过了。

解法二 分治

换一种思想，分治，也就是大问题转换为小问题，通过小问题来解决。

这个想法前边已经做过很多很多题了，大家可以参考 97 题 、115 题 等等。

我们现在要判断目标串 s 是否能由 wordDict 构成。

我们用 dp[i,j)，表示从 s 的第 i 个字符开始，到第 j 个字符的前一个结束的字符串是否能由 wordDict 构成。

假如我们知道了 dp[0,1) dp[0,2) dp[0,3)...dp[0,len - 1) ，也就是除 s 本身的所有子串是否能由 wordDict 构成。

那么我们就可以知道

dp[0,len) = dp[0,1) && wordDict.contains(s[i,len)) || dp[0,2) && wordDict.contains(s[2,len)) || dp[0,3) && wordDict.contains(s[3,len)) ... || dp[0,len - 1) && wordDict.contains(s[len - 1,len)) 

dp[0,len) 就代表着 s 是否能由 wordDict 构成。有了上边的转移方程，就可以用递归写出来了。

public boolean wordBreak(String s, List<String> wordDict) { HashSet<String> set = new HashSet<>(); for (int i = 0; i < wordDict.size(); i++) { set.add(wordDict.get(i)); } return wordBreakHelper(s, set); } private boolean wordBreakHelper(String s, HashSet<String> set) { if (s.length() == 0) { return true; } for (int i = 0; i < s.length(); i++) { if (set.contains(s.substring(i, s.length())) && wordBreakHelper(s.substring(0, i), set)) { return true; } } return false; } 

如果不做任何处理，依旧会得到超时。

所有，memoization 又来了，和之前一样将中间结果存储起来。

public boolean wordBreak(String s, List<String> wordDict) { HashSet<String> set = new HashSet<>(); for (int i = 0; i < wordDict.size(); i++) { set.add(wordDict.get(i)); } return wordBreakHelper(s, set, new HashMap<String, Boolean>()); } private boolean wordBreakHelper(String s, HashSet<String> set, HashMap<String, Boolean> map) { if (s.length() == 0) { return true; } if (map.containsKey(s)) { return map.get(s); } for (int i = 0; i < s.length(); i++) { if (set.contains(s.substring(i, s.length())) && wordBreakHelper(s.substring(0, i), set, map)) { map.put(s, true); return true; } } map.put(s, false); return false; } 

当然除了递归中存储，我们也可以直接用动态规划的思想，求一个结果就保存一个结果。

用 dp[i] 表示字符串 s[0,i) 能否由 wordDict 构成。

public boolean wordBreak(String s, List<String> wordDict) { HashSet<String> set = new HashSet<>(); for (int i = 0; i < wordDict.size(); i++) { set.add(wordDict.get(i)); } boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { dp[i] = dp[j] && set.contains(s.substring(j, i)); if (dp[i]) { break; } } } return dp[s.length()]; } 

总

解法一的回溯优化主要就是剪枝，让一些提前知道结果的解直接结束，不进入递归。解法二的想法，就太常用了，从递归到 memoization 再到动态规划，其实本质都是一样的。