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");
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];
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);
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)。