本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.
题目
给定一个 非空 字符串 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
思路分析
暴力搜索
这道题最开始我们想的肯定是每个字符遍历, 然后去看是不是在wordDict里面。而wordDict是一个list,查找是o(N)的时间复杂度,需要把这个时间复杂度先降下来,用Set把每次查找的时间复杂度降到o(1)。
怎幺去check一个字符串wordDict能不能被组成,一个很朴素的想法就是把每个字符串分作两段,然后递归。比如如下代码。
public class Solution { public boolean wordBreak(String s, List<String> wordDict) { return helper(s, new HashSet<>(wordDict), 0); } public boolean helper(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)) && helper(s, wordDict, end)) { return true; } } return false; } }
很显然这种思路是行不通的,因为时间复杂度太高,有兴趣的同学可以试一下。
时间复杂度: O(n^n)
空间复杂度:O(n)
记忆化搜索
重复计算太多。哪里重复了?举个例子:
输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"] for 循环中: 首次递归: s = 'A' + helper('AAleetcodeB'), 最终检查不符合; 二次递归: s = 'AA' + helper('AleetcodeB'), 最终检查不符合; 三次递归: s = 'AAA' + helper('leetcodeB'), 最终检查不符合;
发现没, 上面每一次都重复计算了 helper('leetcodeB')
。
节省时间的办法也很自然: 要是我们能把搜索过的内容记下来就好了 。记忆有两种办法可供参考:
动态规划
记忆化数组进行搜索
动态规划
我们先看动态规划,动态规划其实很好理解,最重要的是 状态转移方程 。不懂的同学,可以手动模拟一遍基本就理解了。
dp[i]表示[0, i] 子串是否能够由wordDict组成
dp[i] = 对于任意j, dp[j] && wordDict 包含 s[j + 1, i],其中j 属于区间 [0, i] 。
模拟一下动态规划的过程是:
输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"] dp[0] = true 首次dp: dp[1] = true, wordDict 包含'A'; 二次dp: dp[2] = true, dp[1] = true, wordDict 包含'A'; 三次dp: dp[3] = true, dp[1] = true, wordDict 包含'AA'; ... 最后一次dp: dp[12] = false, dp[1]= true wordDict 不包含'AAleetcodeB'; dp[2]= true wordDict 不包含'AleetcodeB'; dp[3]= true wordDict 不包含'leetcodeB'; dp[7]= true wordDict 不包含'codeB'; dp[11]= true wordDict 不包含'B' 故,dp[12] = false.
java版本代码如下:
class Solution { public boolean wordBreak(String s, List<String> wordDict) { if (s == null) return false; Set<String> wordSet = new HashSet<>(); for (int i = 0; i < wordDict.size(); i++) { wordSet.add(wordDict.get(i)); } boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { String current = s.substring(j, i); if (dp[j] && wordSet.contains(current)) { dp[i] = true; break; } } } return dp[s.length()]; } }
时间复杂度:O(n^2)。两层for循环。
空间复杂度: O(n)。dp数组长度是n。
DFS
动态规划和记忆化搜索都是很常用的解法,本题我们可以用一个数组 memoToEndContain
记下位置i到字符串结束能不能够由wordDict组成。还是我们最开始的例子:
输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"] 首次for循环: 'A' 可以被 wordDict组成 'AA' 可以被 wordDict组成 ... 'AAAleetcodeB'不可以被 wordDict组成 这次深搜后记住: 从第一个字母'A' 第二个字母'A', 第三个字母'A' ... 开始的子串都不能由wordDict组成;
java代码:
public class Solution { public boolean wordBreak(String s, List<String> wordDict) { if (s == null) return false; Set<String> wordSet = new HashSet<>(wordDict); Boolean[] memoToEndContain = new Boolean[s.length()]; return dfs(s, 0, wordSet, memoToEndContain); } public boolean dfs(String s, int start, Set<String> wordSet, Boolean[] memoToEndContain) { if (start == s.length()) { return true; } if (memoToEndContain[start] != null) { return memoToEndContain[start]; } for (int end = start + 1; end <= s.length(); end++) { if (wordSet.contains(s.substring(start, end)) && dfs(s, end, wordSet, memoToEndContain)) { return memoToEndContain[start] = true; } } memoToEndContain[start] = false; return memoToEndContain[start]; } }
时间复杂度:O(n^2)。搜索树的大小最多达到 n^2 。
空间复杂度: O(n)。深度优先二叉搜索树深度最多是n。
Be First to Comment