给定一个非空字符串 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 提交记录,这应该没什么问题了。
时间复杂度和空间复杂度还是和上面一样,没有本质区别。
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目主要利用动态规划,复用之前计算的结果,再找出更加合适的边界条件,快速失败,最终得到比较合适的方案。
有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。
https://www.death00.top/
公众号:健程之道
点击此处留言