给定一个非空字符串 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"。注意你可以重复使用字典中的单词。

示例 3:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 – Bottom-up

这道题我们使用动态规划来解决,给定字符串s,声明类型为boolean的数组dp[|s| + 1]dp[i] = true时表示长度为i的字符串能够被拆分为一个或多个在字典中出现的单词,因为这句话太长了,下文简称为“可构成的”。

在填充dp数组时,我们首先变化的是问题规模,即字符串s的前缀长度len。对于长度为len的字符串,我们设置分割点splitIdx,可以写出状态转移公式dp[len] = dp[splitIdx] && s[splitIdx...len) in wordDict,其中splitIdx<len,初始dp[0] = true,表示空串是可构成的。公式的物理意义为如果字符串s的前splitIdx个字符组成的子串s[0…splitIdx)是可构成的(即dp[splitIdx] = true),且s[splitIdx…len)在字典中存在,那么s[0…len)就是“可构成的”。我们不断地增加问题规模(也就是len)并填充dp数组,当len与s长度相同我们就得到了问题的解。

举个例子s = “leetcode”,dp[|s|+1] = dp[9],初始化dp[0] = true,wordDict = {“leet”, “code”}。首先dp[4]=true,因为dp[0] = true, s[0…4) = “leet” in wordDict;dp[8] = true,因为dp[4] && s[4…8) in wordDict。那么最后答案存储在dp[|s|]即dp[8]中值为true,所以leetcode是可构成的。

在实现时,我们将wordDict从List转换为HashSet,这样才能够迅速地查找单词是否存在。时间复杂度为O(n^3),因为双层循环是O(n^2),但是内部有substring操作;空间复杂度为O(n)。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Set<String> wordSet = new HashSet<>(wordDict);

        dp[0] = true;
        for (int len = 1; len <= s.length(); len++) {
            for (int splitIdx = 0; splitIdx < len; splitIdx++) {
                if (dp[splitIdx] && wordSet.contains(s.substring(splitIdx, len))) {
                    dp[len] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

解法2 – Top-down

解法1采用Bottom-up的角度解决问题,较为难以理解。解法2从Top-down的角度解决问题,例如s = “leetcode”,要判断“leetcode”是否可分割,我们要判断:

  • “”可分割且“leetcode”在字典中,或者
  • “l”可分割且“eetcode”在字典中,或者
  • “le”可分割且“eetcode”在字典中,或者
  • “lee”可分割且“tcode”在字典中,或者
  • ……
  • “leetcod”可分割且“e”在字典中

那么要判断“lee”是否可分割:

  • “”可分割且“lee”在字典中,或者
  • “l”可分割且“ee”在字典中,或者
  • “le”可分割且“e”在字典中

对“lee”的求解又是一个子问题,可以按照相同的模式来解决。这明显是一种递归的形式,我们可以使用递归来求解。我们观察到,上述过程存在相同的子问题被重复求解,因此我们可以使用Map<String, Boolean> cache来记录求解过的子问题,避免重复计算。cache需要被初始化,将<“”, true>放入其中。

class Solution {
    private Map<String, Boolean> cache = new HashMap<>();

    public boolean wordBreak(String s, List<String> wordDict) {
        cache.put("", true);
        return wordBreak(s, new HashSet<>(wordDict));
    }

    private boolean wordBreak(String s, Set<String> wordSet) {
        Boolean cached = cache.get(s);
        if (cached != null)
            return cached;

        for (int i = 0; i < s.length(); i++) {
            if (wordBreak(s.substring(0, i), wordSet) && wordSet.contains(s.substring(i))) {
                cached = true;
                break;
            }
        }
        // 如果单词不可分割,那么为false
        if (cached == null)
            cached = false;
        cache.put(s, cached);
        return cached;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *