180 - 140 单词拆分2

题目

给定一个非空字符串 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"] 输出: []

解答

学了回溯，看啥都像可以用回溯的样子

from collections import deque

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        if len(s) == 0:
            return []
        word_set = {word for word in wordDict}
        dp = [0 for _ in range(len(s)+1)]
        dp[0] = 1
        for i in range(1, len(s)+1):
            for j in range(i):
                if dp[j]and s[j:i] in word_set:
                    dp[i] = 1
                    break
        res = []

        def dfs(s, length, word_set, res, path, dp):
            if length == 0:
                res.append(" ".join(path))
                return
            for i in range(length):
                if dp[i]:
                    suffix = s[i:length]
                    if suffix in word_set:
                        path.appendleft(suffix)
                        dfs(s, i, word_set, res, path, dp)
                        path.popleft()
        if dp[-1]:
            queue = deque()
            dfs(s, len(s), word_set, res, queue, dp)
        return res

Runtime: 44 ms, faster than 85.87% of Python3 online submissions for Word Break II.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Word Break II.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        from collections import defaultdict
        if len(s) == 0:
            return []
        cuts = [False]*(len(s)+1)
        cuts[0] = True
        segs = defaultdict(list)
        for i in range(1, len(s)+1):
            for j in range(i):
                rst = cuts[j]and (s[j:i]in wordDict)
                if rst is True:
                    cuts[i] = rst
                    segs[j].append(i)
        ret = []

        def backtrack(segs, start, path, ret):
            if start == len(s):
                ret.append(" ".join(path))
                return True
            else:
                for j in segs[start]:
                    path.append(s[start:j])
                    backtrack(segs, j, path, ret)
                    path.pop()
        if cuts[-1]is True:
            backtrack(segs, 0, [], ret)
        return ret

Runtime: 112 ms, faster than 19.34% of Python3 online submissions for Word Break II.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Word Break II.