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^2)$

  相当于双重循环遍历字符串。

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

  需要记忆空间大小为$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^2)$

  双重循环遍历字符串。

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

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