题目地址:
https://leetcode.com/problems/word-break-ii/
给定一个字符串 s s s,再给定若干单词的列表 A A A,求所有列表中单词拼起来成为 s s s的所有方式。以列表的形式返回,单词之间以空格分开。例如,
s = "catsanddog"
,单词列表为
["cat", "cats", "and", "sand", "dog"]
,那么要返回的就是
["cats and dog", "cat sand dog"]
,单词间以空格隔开。
法1:DFS。可以枚举第一次分割出来的子串,如果这个子串存在于列表里,并且后面能分割成列表里单词的组合,那么就将其分割出来,然后从这个子串后面一位继续DFS。为了能迅速判断后面是否能分割成列表里单词的组合,我们可以预处理一个boolean数组 f [ i ] f[i] f[i]表示 s s s的后 i i i个字符是否能被组合出来。同时为了迅速判断一个字符串是否存在于列表,我们可以用Trie优化。DFS的同时记录路径即可。代码如下:
import java.util.ArrayList;
import java.util.List;
public class Solution {
// 把Trie写出来
class Trie {
class Node {
Node[] nexts;
boolean isWord;
public Node() {
nexts = new Node[26];
}
}
Node root;
public Trie() {
root = new Node();
}
public void insert(String s) {
Node cur = root;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (cur.nexts[ch - 'a'] == null) {
cur.nexts[ch - 'a'] = new Node();
}
cur = cur.nexts[ch - 'a'];
}
cur.isWord = true;
}
public boolean contains(String s) {
Node cur = root;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (cur.nexts[ch - 'a'] == null) {
return false;
}
cur = cur.nexts[ch - 'a'];
}
return cur.isWord;
}
}
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> res = new ArrayList<>();
Trie trie = new Trie();
// 将所有单词加入trie,并且求一下列表里最长单词长度和最短单词长度
int minl = Integer.MAX_VALUE, maxl = 0;
for (String word : wordDict) {
trie.insert(word);
minl = Math.min(minl, word.length());
maxl = Math.max(maxl, word.length());
}
// dp[i]表示s的后i个字符组成的字符串是否能被组合出来
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
// 计算s的后i个字符的字符串是否能被组合出来
for (int i = 1; i <= s.length(); i++) {
// s的后i个字符的字符串是否能被组合出来当且仅当,
// s的后j个字符能组合出来,并且s的后i个字符去掉后j个字符的子串仍然在trie里
for (int j = 0; j <= i; j++) {
// s的后i个字符去掉后j个字符的子串如果长度不符合,就不用判断了
if (i - j >= minl && i - j <= maxl) {
dp[i] = dp[j] && trie.contains(s.substring(s.length() - i, s.length() - j));
// 发现能,就及时退出
if (dp[i]) {
break;
}
}
}
}
dfs(new StringBuilder(), s, 0, dp, trie, res, minl, maxl);
return res;
}
private void dfs(StringBuilder sb, String s, int pos, boolean[] dp, Trie trie, List<String> res, int minl, int maxl) {
// 如果切割完毕了,就将得到的sb去掉最后一个空格后加入res
if (pos == s.length()) {
res.add(sb.substring(0, sb.length() - 1));
return;
}
// 枚举切出s[pos, i]这个子串
for (int i = pos; i < s.length(); i++) {
// 如果这个子串长度符合条件,则进入下一层逻辑
if (i - pos + 1 >= minl && i - pos + 1 <= maxl) {
// 取出切出来的子串
String cur = s.substring(pos, i + 1);
// 如果这个子串存在于trie,并且后面的子串能被切割出来,那就切
if (trie.contains(cur) && dp[s.length() - i - 1]) {
// 将该子串加入sb,后面加上空格
sb.append(cur).append(' ');
// 从i + 1的位置继续搜索
dfs(sb, s, i + 1, dp, trie, res, minl, maxl);
// 回溯的时候恢复现场
sb.setLength(sb.length() - cur.length() - 1);
}
}
}
}
}
时间复杂度是指数级别的,空间复杂度 O ( s + l n ) O(s+ln) O(s+ln), s s s为字符串长度, l l l是列表里最长单词长度, n n n为单词个数。
法2:DFS + 字符串哈希。这里由于要频繁判断 s s s的某个子串是否在wordDict里,最好的办法还是采用字符串哈希。同样可以用动态规划预处理一下,我们这里可以开个boolean数组 f f f,使得 f [ i ] f[i] f[i]是 s s s的长 i i i的前缀是否存在切割方案。那么 f [ i ] = ⋁ 0 ≤ j ≤ i − 1 ( f [ j ] ∧ s [ j : i − 1 ] ∈ A ) f[i]=\bigvee_{0\le j\le i-1} (f[j]\land s[j:i-1]\in A) f[i]=0≤j≤i−1⋁(f[j]∧s[j:i−1]∈A)预处理出 f f f之后DFS可以有剪枝的效果。代码如下:
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
long P = 131;
// 预处理一下s的前缀哈希数组,和P的各个幂次
long[] hashS = new long[s.length() + 1], pow = new long[s.length() + 1];
pow[0] = 1;
for (int i = 0; i < s.length(); i++) {
hashS[i + 1] = hashS[i] * P + s.charAt(i);
pow[i + 1] = pow[i] * P;
}
// 将wordDict里所有字符串的哈希值存进一个哈希表里
Set<Long> set = new HashSet<>();
for (String word : wordDict) {
long hash = 0;
for (int i = 0; i < word.length(); i++) {
hash = hash * P + word.charAt(i);
}
set.add(hash);
}
// 预处理一下s的各个长度的前缀是否存在切割方案
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++) {
if (set.contains(hashS[i] - hashS[j] * pow[i - j])) {
dp[i] |= dp[j];
// 一旦算出存在方案,就可以退出循环了
if (dp[i]) {
break;
}
}
}
}
List<String> res = new ArrayList<>();
if (!dp[s.length()]) {
return res;
}
dfs(s.length() - 1, s, new ArrayList<>(), set, dp, hashS, pow, res);
return res;
}
private void dfs(int pos, String s, List<String> list, Set<Long> set, boolean[] dp, long[] hashS, long[] pow, List<String> res) {
if (pos == -1) {
StringBuilder sb = new StringBuilder();
for (int i = list.size() - 1; i >= 0; i--) {
sb.append(list.get(i)).append(' ');
}
res.add(sb.substring(0, sb.length() - 1));
return;
}
for (int i = pos; i >= 0; i--) {
if (dp[i] && set.contains(hashS[pos + 1] - hashS[i] * pow[pos - i + 1])) {
list.add(s.substring(i, pos + 1));
dfs(i - 1, s, list, set, dp, hashS, pow, res);
list.remove(list.size() - 1);
}
}
}
}
时空复杂度一样。