原题
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
原题url：https://leetcode-cn.com/problems/word-break/
解题
暴力法
我拿到这道题目时，第一个想到的就是暴力法，从下标0开始，每一个字母都去找，如果找到，就以当前的结尾下标作为下一次的开始下标，继续查找，看起来还是很简单的。
让我们来看看代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 暴力法，从第一个字母开始尝试，长度递增，如果wordDict中存在，则继续往后找，直到找到最后一个字母
return dfs(s, new HashSet<>(wordDict), 0);
}
/**
* s：待查找的字符串
* wordDict：字典集合
* start：本次查找开始的下标
*/
public boolean dfs(String s, Set<String> wordDict, int start) {
// 全部查找完成
if (start == s.length()) {
return true;
}
for (int end = start + 1; end <= s.length(); end++) {
// 当前单词包含在字典表中，并且一路查下去，都能找到
if (wordDict.contains(s.substring(start, end)) && dfs(s, wordDict, end)) {
return true;
}
}
return false;
}
}
提交之后，报超出时间限制，我们分析一下，既然是暴力解法，针对特殊情况，一定效率很低。
在我们这里，那就是如果原字符串s里包含一连串相同的字母，比如：aaaaaaaaaaaaaaaaaaqqqq，并且字典里有一项就是相匹配的单个字母，比如：a，那么这个递归查找，就会针对每一个下标都去寻找一次，并且一旦失败，在下一次遍历中，又会重新查找一遍。
这时我们进行复杂度分析：
- 时间复杂度为：
O(n^n)，其中，n代表原字符串s的长度，此时就是最坏的情况。 - 空间复杂度为：
O(n)，这代表递归回溯时，最多只会有 n 个调用栈同时存在。
初步优化——利用之前的结果
既然上面说每次失败后，都会重新进行查找，并且明显存在重复，那么我们这一次优化的目标，就是尽可能利用之前的结果，那么该如何利用呢？
因为我们这是在从前向后查找，那么可以想到的就是后缀匹配，也就是利用一个记忆数组，记录每一个节点到最后一个节点是否是可以被查到的，这样在进行第一次遍历的时候，就可以得出一些中间结果，被使用到之后的查找中。
让我们来看看代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 记忆回溯，增加一个后缀记忆的Boolean数组，当下标i的值为true，说明从i开始可以一直找到最后，这样针对后缀可以避免重复查找
return dfs(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
}
/**
* s：待查找的字符串
* wordDict：字典集合
* start：本次查找开始的下标
* suffixMemoryArray：记忆后缀数组，当下标i的值为true，说明从i开始可以一直找到最后
*/
public boolean dfs(String s, Set<String> wordDict, int start, Boolean[] suffixMemoryArray) {
// 全部查找完成
if (start == s.length()) {
return true;
}
// 从当前start是否可以直接找到最后，不等于null，说明已经查找过了，直接利用之前的结果
if (suffixMemoryArray[start] != null) {
return suffixMemoryArray[start];
}
for (int end = start + 1; end <= s.length(); end++) {
// 当前单词包含在字典表中，并且一路查下去，都能找到
if (wordDict.contains(s.substring(start, end)) && dfs(s, wordDict, end, suffixMemoryArray)) {
// 说明从当前start能一直从字典中找完
suffixMemoryArray[start] = true;
return true;
}
}
suffixMemoryArray[start] = false;
return false;
}
}
提交OK，执行用时：6 ms，内存消耗：37 MB，执行用时只战胜了73.92%的 java 提交记录，看来还可以继续优化。
让我们再看一下复杂度：
- 时间复杂度：
O(n^2)，因为可以利用之前的结果，最多只是进行双重 for 循环。 - 空间复杂度为：
O(n)，这个和之前一样的。
继续优化——后缀改为前缀
之前用的是后缀记忆，那么能不能用前缀记忆呢？这就相当于把问题拆分，原本的字符串s，拆分为前部分s1和后部分s2，如果s1和s2都能被找到，则说明s能被找到，然后继续拆分。
将前缀查找过的部分，也记录下来。我们来看看代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 动态规划，将原本的s拆分为s1和s2，如果s1和s2都包含，则认为s是可以的，本质是前缀匹配
// 字典集合
Set<String> wordDictSet = new HashSet<>(wordDict);
// 后缀记忆，默认prefixMemoryArray[0]是存在于字典中的，因为0代表着空，下标为i时，代表从0到i的字符可以直接或者被拆分后在wordDict中找到
boolean[] prefixMemoryArray = new boolean[s.length() + 1];
prefixMemoryArray[0] = true;
// 遍历
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (prefixMemoryArray[j] && wordDictSet.contains(s.substring(j, i))) {
prefixMemoryArray[i] = true;
}
}
}
return prefixMemoryArray[s.length()];
}
}
提交OK，执行用时：7 ms，内存消耗：36.4 MB，执行用时只战胜了56.96%的 java 提交记录，还不如上面那种，只是在空间上有所优化，毕竟将递归改造了一下，看来还可以继续优化。
让我们再看一下复杂度：
- 时间复杂度：
O(n^2)，还是和之前一样的。 - 空间复杂度为：
O(n)，这个和之前一样的。
最终优化——找出快速失败的条件
感觉思路上应该没有问题，估计在边界判定时有一些点我们可能还没有看到。
既然是要在字典集合中存在，那么如果需要查找的字符串太长或太短肯定都不可以，即不可以超过字典里最长的单词，也不可以少于字典里最短的单词。
针对上面的解法，就是：
- j 的初始值应该是 0 和 (i - max) 中的最大值，因为如果 j 太小，那么后续需要查找的字符串可能太长，那么就没必要找了。
- j 的最大值应该是 (i - j >= min)，因为如果后续需要查找的字符串可能太短，也没必要查找了。
让我们看看代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 动态规划，将原本的s拆分为s1和s2，如果s1和s2都包含，则认为s是可以的，本质是前缀匹配
// 字典集合
Set<String> wordDictSet = new HashSet<>();
// 找出wordDict中最大长度和最小长度
int max = 0;
int min = Integer.MAX_VALUE;
for (String word : wordDict) {
if (word.length() > max) {
max = word.length();
}
if (word.length() < min) {
min = word.length();
}
wordDictSet.add(word);
}
// 后缀记忆，默认prefixMemoryArray[0]是存在于字典中的，因为0代表着空，下标为i时，代表从0到i的字符可以直接或者被拆分后在wordDict中找到
boolean[] prefixMemoryArray = new boolean[s.length() + 1];
prefixMemoryArray[0] = true;
// 遍历
for (int i = 1; i <= s.length(); i++) {
// 如果需要查找的长度大于最大值或者小于最小值，就没必要继续找了
for (int j = Math.max(0, i - max); i - j >= min; j++) {
if (prefixMemoryArray[j] && wordDictSet.contains(s.substring(j, i))) {
prefixMemoryArray[i] = true;
}
}
}
return prefixMemoryArray[s.length()];
}
}
提交OK，执行用时：2 ms，内存消耗：34.4 MB，执行用时战胜了97.96%的 java 提交记录，这应该没什么问题了。
时间复杂度和空间复杂度还是和上面一样，没有本质区别。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题目主要利用动态规划，复用之前计算的结果，再找出更加合适的边界条件，快速失败，最终得到比较合适的方案。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道
