LeetCode_128_WordBreak

1. question: 单词拆分（中等）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

2. answers

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

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

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

代码如下所示：

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));
    }
}

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

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)。