转载

力扣139——单词拆分

原题

给定一个非空字符串 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 ,如果 s1s2 都能被找到,则说明 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 提交记录,这应该没什么问题了。

时间复杂度和空间复杂度还是和上面一样,没有本质区别。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目主要利用动态规划,复用之前计算的结果,再找出更加合适的边界条件,快速失败,最终得到比较合适的方案。

有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。

https://www.death00.top/

公众号:健程之道

力扣139——单词拆分

点击此处留言

原文  http://mp.weixin.qq.com/s?__biz=MzU0NTk3NDMyMQ==&mid=2247483968&idx=1&sn=ea832526ef9d92a03680eb1de3f6930b
正文到此结束
Loading...