Leetcode 140 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”]
输出:
[]

分析：

  1. 标准的回溯思想，我们先从暴力法开始分析，直接遍历wordDict中的每个字符串word，看是否满足s.startwith(word)，若满足再重新开始遍历，这样的话时间复杂度应该是O(kn^2)，其中n为wordDict长度，k为word平均长度。这样显然复杂度太高。
  2. 那么我们容易想到，使用一个字典根据每个单词的首字母来存储，这样我们可以只遍历以s[0]开头的word，这样平均复杂度能够到O(kn)，但若wordDict中大量单词是以同一字母开头，复杂度在最坏情况下仍会是O(kn^2)。但单就这道题来说，这样优化之后是可以通过的。
  3. 在这道题中还有一点无法处理，那就是在上述最坏情况下，s实际上并不能用wordDict构建，这种情况也会导致TLE，故在开始时先判断s是否能有wordDict表示(借鉴于discuss)

思路：

  1. 定义breakable函数判断s是否可分
  2. 建立字典根据首字母存储wordDict中单词及长度(用来分片)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        # 回溯很简单，关键在于判断这个字符串本身是否可分，如若不能，会有大量重复计算，避免这一点就不会TLE
        def breakable():
            rightmosts = [0]
            for i in range(1, len(s) + 1):
                for last_index in rightmosts:
                    if s[last_index:i] in words:
                        rightmosts.append(i)
                        if i == len(s): 
                            return True
                        break
            return False
        words = set(wordDict)
        if not breakable(): return []
        
        d = collections.defaultdict(list)
        for word in wordDict:
            d[word[0]].append((word,len(word)))

        # 标准回溯代码写法
        def helper(s,rec='',res=[]):
            if not s:
            	# rec右边多一个空格
                res.append(rec.rstrip())
                return
            for word,c in d[s[0]]:
                if s.startswith(word):
                    helper(s[c:],rec+word+' ',res)

        res = []
        helper(s,'',res)
        return res

39 / 39 test cases passed.
difficulty: hard
Runtime: 52 ms,beats 94.64%