LeetCode_128_WordBreak


1. question: 单词拆分(中等)

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/word-break

示例 1:

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

示例 2:

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意,你可以重复使用字典中的单词。

示例 3:

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示:

1
2
3
4
5
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

2. answers

这道题虽然是单词拆分,但是可以看成是子串拼接。也就是完全背包问题。但是要拼接成字符串,子串的选择肯定是有顺序的,因此可看成是排列问题。

定义数组dp[j]表示在当前容量下,所有子串所能形成的最长的、且符合字符串前缀的子串。

因此递推公式仍然是【不选本物品,选本物品】二者选最长的子串。

代码如下所示:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Solution_0128 {

public boolean wordBreak(String s, List<String> wordDict) {

String[] dp = new String[s.length() + 1];

// 初始化
Arrays.fill(dp, "");
dp[0] = "";

// 动态规划,注意排列是外层遍历容量,内层遍历物品
for (int i = 0; i < dp.length; i++) {

for (int j = 0; j < wordDict.size(); j++) {

String strs = wordDict.get(j);

// 能加入本元素
// 注意,加入本元素,不仅需要长度足够,而且还需要加入后能够匹配字符串前缀
if(i >= strs.length() && s.indexOf(dp[i - strs.length()] + strs) == 0) {

// 而且还要和原始比较,取最长的
String temp = dp[i - strs.length()] + strs;
dp[i] = dp[i].length() >= temp.length() ? dp[i] : temp;
}
}

}

return dp[s.length()].equals(s);
}

public static void main(String[] args) {
System.out.println();

Solution_0128 s = new Solution_0128();

String strs = "leetcode";
List<String> wordDict = new ArrayList<>();
wordDict.add("leet");
wordDict.add("code");

// String strs = "applepenapple";
// List<String> wordDict = new ArrayList<>();
// wordDict.add("apple");
// wordDict.add("pen");

// String strs = "catsandog";
// List<String> wordDict = new ArrayList<>();
// wordDict.add("cats");
// wordDict.add("dog");
// wordDict.add("sand");
// wordDict.add("and");
// wordDict.add("cat");

// String strs = "aaaaaaa";
// List<String> wordDict = new ArrayList<>();
// wordDict.add("aaaa");
// wordDict.add("aaa");

System.out.println(s.wordBreak(strs, wordDict));
}
}

其实似乎可以优化一下,即没必要存储字符串,只需要存储形成字符串的最后一个下标即可。代码如下所示:

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
public boolean wordBreak(String s, List<String> wordDict) {

int[] dp = new int[s.length() + 1];

// 初始化
// 注意,初始化为-1,表示还没有生成字符串,即下次比较要从 -1 + 0 开始匹配。
Arrays.fill(dp, -1);
dp[0] = -1;

// 动态规划,注意排列是外层遍历容量,内层遍历物品
for (int i = 0; i < dp.length; i++) {

for (int j = 0; j < wordDict.size(); j++) {

String strs = wordDict.get(j);

// 能加入本元素
// 注意,加入本元素,不仅需要长度足够,而且还需要加入后能够匹配字符串前缀
// 根据dp[i - strs.length()]所形成的子串的最后一个位置开始找本单词
if(i >= strs.length()) {

int pre = dp[i-strs.length()];

if(s.substring(pre + 1, pre + 1 + strs.length()).equals(strs)) {

// 而且还要和原始比较,取最长的
// 这里存储的是下标
dp[i] = Math.max(dp[i], pre + 1 + strs.length() - 1);
}

}
}

}

return dp[s.length()] == s.length() - 1;

}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录