LeetCode 热题 HOT 100 Java题解——139. 单词拆分

LeetCode 热题 HOT 100 Java题解

139. 单词拆分记忆化回溯复杂度分析 记忆化搜索 + 字符串哈希优化复杂度分析 动态规划复杂度分析

139. 单词拆分

题目：

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

说明：

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

示例：

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

记忆化回溯

首先将字典$List$加入到$HashSet$当中，这样每次判断有无单词均摊时间为$O(1)$。

逐个增加单词的字符数量，直到字典中有了该单词之后，递归判断剩下的字符串，如果无法匹配返回$false$，如果最后剩下空字符串说明全部匹配成功返回$true$。由于$java$的$subString$生成了新的字符串对象，因此不会对原来的字符串产生影响，因此回溯之后不需要做任何处理来复原原状态。

import java.util.HashSet; import java.util.List; import java.util.Set; class Solution { public boolean backtrack(String s, Set<String> set) { if (s.length() == 0) return true; for (int i = 0; i < s.length(); i++) { if (set.contains(s.substring(0, i + 1))){ if (backtrack(s.substring(i + 1), set)) return true; } } return false; } public boolean wordBreak(String s, List<String> wordDict) { Set<String> set = new HashSet<>(wordDict); return backtrack(s, set); } }

但是这样做会有很多重复计算，因此超出了时间限制，于是想到增加记忆化。

增加一个$boolean$数组表示当前位置之后的字符串是否遍历过了，如果遍历过了并且没有提前递归的返回$true$说明，这个位置后面的匹配是不会成功的，因此直接返回$false$。

import java.util.HashSet; import java.util.List; import java.util.Set; class Solution { boolean[] mem; public boolean backtrack(String s, int start, Set<String> set) { if (s.length() == 0) return true; if (mem[start]) return false; for (int i = 0; i < s.length(); i++) { if (set.contains(s.substring(0, i + 1))){ if (backtrack(s.substring(i + 1), start + i + 1, set)) return true; } } mem[start] = true; return false; } public boolean wordBreak(String s, List<String> wordDict) { this.mem = new boolean[s.length()]; Set<String> set = new HashSet<>(wordDict); return backtrack(s, 0, set); } }

复杂度分析

时间复杂度：$O(n^3)$

相当于双重循环遍历字符串，注意substring方法的复杂度为$O(n)$,因此总复杂度为$O(n^3)$。

空间复杂度：$O(n)$

需要记忆空间大小为$n$。

记忆化搜索 + 字符串哈希优化

tips：感谢评论区大佬@lpf-4k的点拨，java string的substring方法为$O(n)$复杂度，因此想要优化这部分的复杂度，要使用字符串哈希算法。

简单来说，字符串哈希就是将一个长的字符串的前缀字符串哈希算出来，如果想求得某个区间$[l,r]$的子串哈希，只需要将$[0,l]$的字符串向左移$r-l+1$位，即乘上一个因子（代码中为了简化计算，所有长度的因子已经提前计算好放到了$p[]$当中），这样的话就可以在$O(1)$的时间复杂度内，求出子串是否和字典中的字符串相等。

注意：这里因子$P$取31的原因是，java的hashCode()方法因子取值同为31，这样在计算字典中每个单词的哈希的时候就可以直接使用该方法了。

这里不会把字符串哈希的思想讲的很明白，大家可以自行搜索下相关资料，学习一下，字符串哈希同样可以用于字符串匹配当中（https://leetcode-cn.com/problems/implement-strstr/solution/java-kmp-zi-fu-chuan-ha-xi-liang-chong-fang-fa-by-/）。

import java.util.HashSet; import java.util.List; import java.util.Set; class Solution { boolean[] mem; int[] h, p; int P = 31; Set<Integer> set = new HashSet<>(); public int getSubHash(int l, int r){ return h[r] - h[l - 1] * p[r - l + 1]; } public void stringHash(String s, List<String> wordDict){ char[] str = s.toCharArray(); h = new int[str.length + 1]; p = new int[str.length + 1]; p[0] = 1; for(int i = 1; i <= str.length; i++){ h[i] = h[i - 1] * P + str[i - 1]; p[i] = p[i - 1] * P; } for(String ss : wordDict){ set.add(ss.hashCode()); } } public boolean backtrack(String s, int start) { if (start == s.length()) return true; if (mem[start]) return false; for (int i = start; i < s.length(); i++) { if (set.contains(getSubHash(start + 1, i + 1))){ if (backtrack(s, i + 1)) return true; } } mem[start] = true; return false; } public boolean wordBreak(String s, List<String> wordDict) { this.mem = new boolean[s.length()]; stringHash(s, wordDict); return backtrack(s, 0); } }

复杂度分析

时间复杂度：$O(n^2)$

使用字符串哈希优化后复杂度为$O(n^2)$。

空间复杂度：$O(n)$

需要额外数组大小都为$O(n)$量级。

动态规划

$dp[i]$表示$i$位之前的字符串是否可以被拆分，因此$dp[0]=true$表示空串是可以被拆分成功的：

计算$dp[i]$：

需要一个内层循环$j$，相当于需要判断：

KaTeX parse error: Expected 'EOF', got '&' at position 13: dp[i]=dp[j] &̲& check(s[j..i−…

也就是如果$j$之前的可以拆分就判断$j..i-1$是否在字典中，在为$true$不在为$false$。最后返回$dp[s.length()]$即可。

import java.util.HashSet; import java.util.List; import java.util.Set; class Solution { public boolean wordBreak(String s, List<String> wordDict) { boolean[] dp = new boolean[s.length() + 1]; Set<String> set = new HashSet<>(wordDict); dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && set.contains(s.substring(j, i))){ dp[i] = true; break; } } } return dp[s.length()]; } }

复杂度分析

时间复杂度：$O(n^3)$

同上。

空间复杂度：$O(n)$

需要额外$dp$数组大小为$n$。

我的博客：https://me.csdn.net/qq_20067165?ref=miniprofile