题目
给定一个非空字符串
s
和一个包含非空单词列表的字典wordDict
,判定s
是否可以被空格拆分为一个或多个在字典中出现的单词。说明:
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1:
1
2
3 输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2:
1
2
3
4 输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。示例 3:
1
2 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
审题
关键词:非空字符串、非空列表
问题:是否可以用空格拆分字符串为非空列表中的子字符串
P.S. 可重复使用列表元素、列表元素无重复
分析
暴力法
从头开始遍历字符串,标记头尾(尾后),每次移动尾后指针,在字典中查找头尾指针标记的字符串,如果查找命中,则将头指针移动到尾后指针位置,尾后指针向后移动,最后如果头尾指针不相等,那么返回false,否则返回true。
因为要遍历字符串,假设字符串长度为$N$,字典长度$M$,那么每次移动尾指针都需要查找字典,如果使用哈希表,就能使得每次查找的时间复杂度为$O(1)$,从而使得整体时间复杂度$O(N)$,空间复杂度$O(max(M,N))$。
在写程序的时候发现有漏洞:如果字典中的字符串存在嵌套的情况,且开头相同结尾不同时,我们的逻辑就会提前找到短的匹配字符串而忽略长的,从而出错。
要修复这个bug则需要更复杂的逻辑。
事实上,暴力法是使用递归和回溯完成的。基于我们以上的逻辑,使用递归的思想:如果我们在字典中找到了当前子字符串,那么当剩余字符串可以被字典中的单词拆分的时候,整个字符串可以被单词拆分。这样其实利用的是递归的思想。
代码:
1 | // 29 / 36 个通过测试用例,(超过时间限制) |
- 时间复杂度:对于长度为$N$的字符串,最坏情况递归深度为$N$,而函数对自身的递归调用又在长度为$N$的循环中,这相当于每次递归会调用自己$N$次,而不是一次,那么时间复杂度为$O(N^N)$;
- 空间复杂度$O(N)$
记忆化回溯
暴力法中,会对相同字符串调用多次回溯函数,因为每次递归都是对嵌套子结构的计算,这中间必然有重复计算。那么我们采用记忆化回溯,也就是对回溯树进行剪枝,这样只需遍历所有可能的子字符串,时间复杂度优化为$O(N^2)$,空间复杂度$O(N)$。
1 | class Solution { |
动态规划
一个给定字符串是否可以拆分成字典中的单词?
这个问题是否是一个具有重复结构的子问题?是。一个可拆分的字符串一定由两个可拆分的字符串组成。对于字符串中的一个字符,以该字符结尾的字符串如果可拆分,而且之后的字符串也可拆分。对此进行动态规划,实际上就是记忆化回溯的迭代版本。
总结
通过这道题发现自己不是很分得清动态规划和回溯,需要进行深入理解。