LeetCode 热题 HOT 100 Java题解——139. 单词拆分_java100个号码,判断有多少个139,139可能出现在任何位置

139. 单词拆分

题目：

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

说明：

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

示例：

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

记忆化回溯

首先将字典$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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

增加一个$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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

• 时间复杂度：$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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

复杂度分析

• 时间复杂度：$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()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度分析

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

  同上。

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

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

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