LeetCode——单词拆分I&II

单词拆分中等、单词拆分II 困难

NO.139 单词拆分中等

思路一：动态规划 dp[i]的含义：s 的[0,i]字符区间形成的子串是否可以被拆分成字典中的单词。

初始化：dp[s.length+1] 包含空串，dp[0]=true，即空串符合要求。

状态转移：dp[i]=i >= len && dp[i - len] && s.substring(i - len, i).equals(word)，即遍历 wordDict 的每一个 word,判断 word 是否位于[0,i]子串末尾，并且 word 单词之前的子串也符合要求，全部都满足的情况下，[0,i]子串才可以被拆分成字典中的单词。

public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dp = new boolean[s.length()+1];
    dp[0]=true;
    for (int i = 1; i <= s.length(); i++) {
        for (String word : wordDict) {
            int len = word.length();
            if (i >= len && dp[i - len] && s.substring(i - len, i).equals(word)) {
                dp[i]=true;
                break;
            }
        }
    }
    return dp[s.length()];
}

时间复杂度：O(n*m) n字符串长度，m字典中单词个数。

NO.140 单词拆分II 困难

思路一：动态规划+递归 关键是用一个 HashMap 作为缓存，存储 S 的所有中间子串的拆分结果，大大减少了中间重复的运算。就是所谓的memoization 技术。

public List<String> wordBreak(String s, List<String> wordDict) {
    //取得字典中最长单词的长度
    int maxLen = 0;
    //字典存入 HashSet 中加快查找
    HashSet<String> dict = new HashSet<>();
    for (String word : wordDict) {
        dict.add(word);
        maxLen = Math.max(maxLen, word.length());
    }
    return helper(s, maxLen, dict, new HashMap<String, LinkedList<String>>());
}

private List<String> helper(String s, int maxLen, HashSet<String> wordDict, HashMap<String, LinkedList<String>> cache) {
    //如果已经求过 S 的分割结果,直接将结果返回
    if (cache.containsKey(s)) return cache.get(s);
    LinkedList<String> res = new LinkedList<>();
    //S 为空，不需要拆分
    if (s.length() == 0) {
        res.add("");
        return res;
    }
    // S 的[0,i]子串
    for (int i = 0; i < s.length(); i++) {
        //子串是字典中的单词
        if (i < maxLen && wordDict.contains(s.substring(0, i + 1))) {
            //遍历, [i+1,n] 字符串递归生成的拆分结果
            for (String temp : helper(s.substring(i + 1), maxLen, wordDict, cache)) {
                // [0,i]单词和后序的拆分结果依次组合
                res.add(s.substring(0, i + 1) + (temp.isEmpty() ? "" : " ") + temp);
            }
        }
    }
    //S 和 S的拆分结果 放入缓存后返回
    cache.put(s, res);
    return res;
}

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.139 单词拆分 中等

NO.140 单词拆分II 困难

NO.139 单词拆分中等