回溯算法：单词拆分

140. 单词拆分 II

139. 单词拆分

今天来介绍「单词拆分」的两个题目，题目意思很容易理解。这里给出的两个题目「单词拆分」「单词拆分 II」的要求也基本一致，唯一不同的只有返回的内容

对于「单词拆分」难度「Medium」，题目只要求返回true / false，即判断是否可以拆分即可

对于「单词拆分 II」难度「Hard」，题目要求返回所有拆分的组合

单词拆分 II

这里先讲难度更大的「单词拆分 II」。其实这个题目给的数据量没有那么大，所以就是很基本的「回溯」框架模版！关于回溯详细讲解可见 回溯 (DFS) 算法框架

我感觉这个题目虽然难度为 Hard，但其实并没有「单词拆分」难，因为不需要优化，哈哈哈哈哈哈

每次写「回溯」题目时，就要思考三个问题：

• 路径：已经做出的选择
• 选择列表：当前可以做的选择
• 结束条件：到达决策树底层，无法再做选择的条件

我们现在结合样例s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]，来梳理一下上面的三个问题！！

首先，我们的「结束条件」是什么？显然是当我们把s全部遍历完之后就可以结束

其次，我们的「选择列表」是什么？显然是wordDict中的单词集合

最后，我们的「路径」是什么？显然是我们每一步从wordDict中选择的单词集合

上面这么说可能有些晦涩难懂，直接上「回溯树」叭！！

可以很明显的看出需要剪枝的是在wordDict中找不到对应单词的分支

​x
class Solution {
    // 快速判断是否存在某个单词
    private Set<String> wordSet = new HashSet<>();
    private List<String> res = new ArrayList<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        for (String word : wordDict) wordSet.add(word);
        backtrack(s, 0, new LinkedList<>());
        return res;
    }

    private void backtrack(String s, int start, LinkedList<String> track) {
        // 满足条件，存储当前路径
        if (start == s.length()) {
            // 用空格相连
            res.add(String.join(" ", track));
            return ;
        }
        for (int i = start; i < s.length(); i++) {
            // 切分字符串
            String word = s.substring(start, i + 1);
            // 不在 wordSet 中，则跳过
            if (!wordSet.contains(word)) continue;
            
            // 添加到路径中
            track.addLast(word);

            backtrack(s, i + 1, track);
            
            // 撤销操作
            track.removeLast();
        }
    }
}

至此，这个题目就可以完美通过！是不是感觉「Hard」也没有那么难

单词拆分

这个题目乍一看，比上面的那个题目还简单很多，上一个题目的代码完全可以复用，稍微改改就行！代码如下：

xxxxxxxxxx
private boolean ok = false;
private Set<String> wordSet = new HashSet<>();
public boolean wordBreak(String s, List<String> wordDict) {
    for (String word : wordDict) wordSet.add(word);
    backtrack(s, 0);
    return ok;
}
private void backtrack(String s, int start) {
    if (ok) return ;
    if (start == s.length()) {
        ok = true;
        return ;
    }
    for (int i = start; i < s.length(); i++) {
        String subStr = s.substring(start, i + 1);
        if (!wordSet.contains(subStr)) continue;

        backtrack(s, i + 1);

    }
}

可是，无奈超时了！！！然后对比了一下两个题目的数据量，明显本题的数据量更大一些，所以肯定需要优化！

现在怎么优化呢？？？突然灵感乍现，想到了之前写过的一个题目的优化策略，记录「状态」。详情可见 经典回溯算法：集合划分问题

结合上述优化策略，具体分析本问题。先给出一个样例：s = "abcd...", wordDict = ["a","b","c","ab","bc"]

显然这个样例是无法拆分成单词的，我们来模拟一下部分过程：

当我们处于下图的状态时，显然需要回溯，因为后面的部分[d...]无法拆分

在回溯的过程中，肯定会出现两种状态，如下图：

到达这两种状态后，我们依然不知道[d...]部分的字符串是否可以拆分成单词。所以就需要递归处理[d...]，显然这就存在「重复子问题」了

因为我们在第一次的时候已经处理过了[d...]，而且知道[d...]是无法拆分成单词的，只是我们没有记录该子问题的结果而已

经过上面的分析，显然就知道如何优化了！！！直接看代码：

xxxxxxxxxx
// 记录 [i...n-1] 是否可以拆分成单词
// 0 : 表示还未处理该子问题；1 : 表示可以；-1 : 表示不可以
private int[] emeo;
private Set<String> wordSet = new HashSet<>();
public boolean wordBreak(String s, List<String> wordDict) {
    for (String word : wordDict) wordSet.add(word);
    emeo = new int[s.length()];
    Arrays.fill(emeo, 0);
    return backtrack(s, 0);
}
private boolean backtrack(String s, int start) {
    if (start == s.length()) return true;
    // 如果子问题已经处理过了，直接返回结果
    if (emeo[start] != 0) return emeo[start] == 1;
    for (int i = start; i < s.length(); i++) {
        String subStr = s.substring(start, i + 1);
        if (!wordSet.contains(subStr)) continue;

        boolean subRes = backtrack(s, i + 1);
        if (subRes) {
            // 说明 [start...n-1] 是可以拆分成单词的
            emeo[start] = 1;
            return true;
        }
    }
    // 已经完整遍历 [start...n-1] 都无法拆分
    emeo[start] = -1;
    return false;
}