[LeetCode] 140. 单词拆分 II

题目链接 : https://leetcode-cn.com/problems/word-break-ii/

题目描述:

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例:

示例 1：

输入:

s = "catsanddog"

wordDict = ["cat", "cats", "and", "sand", "dog"]

输出:

[

  "cats and dog",

  "cat sand dog"

]

示例 2：

输入:

s = "pineapplepenapple"

wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

输出:

[

  "pine apple pen apple",

  "pineapple pen apple",

  "pine applepen apple"

]

解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

输出:

[]

思路:

动态规划:

自顶向下:

参照139. 单词拆分 | 题解链接

代码:

思路一:

class Solution:

    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:

        import functools

        if not wordDict:return []

        wordDict = set(wordDict)

        max_len = max(map(len, wordDict))

        @functools.lru_cache(None)

        def helper(s):

            res = []

            if not s:

                res.append("")

                return res

            for i in range(len(s)):

                if i < max_len and s[:i+1] in wordDict:

                    for t in helper(s[i+1:]):

                        if not t:

                            res.append(s[:i+1])

                        else:

                            res.append(s[:i+1] + " " + t)

            return res

        return helper(s)

java

class Solution {

    public List<String> wordBreak(String s, List<String> wordDict) {

        int max_len = 0;

        for (String word : wordDict) max_len = Math.max(max_len, word.length());

        return helper(s, max_len, wordDict, new HashMap<String, LinkedList<String>>());

    }

    private List<String> helper(String s, int max_len, List<String> wordDict, HashMap<String, LinkedList<String>> cache) {

        if (cache.containsKey(s)) return cache.get(s);

        LinkedList<String> res = new LinkedList<>();

        if (s.length() == 0) {

            res.add("");

            return res;

        }

        for (int i = 0; i < s.length(); i++) {

            if (i < max_len && wordDict.contains(s.substring(0, i + 1))) {

                for (String tmp : helper(s.substring(i + 1), max_len, wordDict, cache))

                    res.add(s.substring(0, i + 1) + (tmp.isEmpty() ? "" : " ") + tmp);

            }

        }

        cache.put(s, res);

        return res;

    }

}

巴特西

[LeetCode] 140. 单词拆分 II

题目描述:

示例:

思路:

代码:

最新文章

热门文章