力扣139——单词拆分

这道题主要就是利用动态规划，能够利用上之前的结果，进行优化。

原题

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1 2	输入: 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()];
    }
}