139. 单词拆分

题目

  /**
     * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
     * 说明：
     * 拆分时可以重复使用字典中的单词。
     * 你可以假设字典中没有重复的单词。
     *
     * 示例 1：
     * 输入: s = "leetcode", wordDict = ["leet", "code"]
     * 输出: true
     * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
     * 
     * 示例 2：
     * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
     * 输出: true
     * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     * 注意你可以重复使用字典中的单词。
     */

思路:

• 1.这是一个完全背包问题,本题可以转换为是否可以用现有单词拼成该字符串
• 2.我们可以把问题逐步拆分,比如一个applepenapple,我们可以先看applepen可不可以组成,applepen可以组成applepenapple就等于applepen和apple,以此递推

代码:

   public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);

        boolean[] hasCheck = new boolean[s.length() + 1];

        //hasCheck[i]表示：字符串的前i个字符是否可以由背包中的单词组成
        hasCheck[0] = true;

        // 如果确定hasCheck[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dphasChecki]一定是true。（j < i ）。
        // 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && hasCheck[j]是true) 那么 dp[i] = true。

        for (int i = 1; i <= s.length(); i++) {
            //倒着遍历，考虑到单词长度可能远小于target长度，倒着遍历效率更高
            for (int j = i - 1; j >= 0; j--) {
                if (!hasCheck[j]) {
                    continue;
                }

                if (hasCheck[j] && words.contains(s.substring(j, i ))) {
                    hasCheck[i] = true;
                    break;
                }
            }
        }

        return hasCheck[s.length()];
    }