Skip to content

140 word break ii

140. Word Break II

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

难度:

Medium

还是backtracking,会超时

class Solution(object):  # 此法超时
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        self.res = []
        self.wordBreakLst("",s,wordDict)
        return self.res


    def wordBreakLst(self, lst, rest, wordDict):
        if rest == '':
            self.res.append(lst.rstrip())
            # print lst
        for i in range(1+len(rest)):
            if rest[:i] in wordDict:
                self.wordBreakLst(lst + rest[:i] + " ",rest[i:],wordDict)

然后看到有把word break i 结合起来减少时间复杂度的作法。

做法如下,聪明:

就是对于每一个s,我们来check它是否可以break,如果不可以,就不用做相应的操作了

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        self.res = []
        self.wordBreakLst(s, wordDict, '')
        return self.res

    def check(self, s, wordDict):
        ok = [True]
        for i in range(1, len(s) + 1):
            ok += any(ok[j] and s[j:i] in wordDict for j in range(i)),
        return ok[-1]


    def wordBreakLst(self, s, wordDict, stringLst):
        if self.check(s, wordDict):
            if len(s) == 0 : self.res.append(stringLst[1:])  # 因为最开始也加了一个空格
            for i in range(1,len(s)+1):
                if s[:i] in wordDict:
                    self.wordBreakLst(s[i:], wordDict, stringLst + ' ' + s[:i])

但是其实

s = "aaaaaa"
wordDict = ["a","aa","aaa"]
print a.wordBreak(s,wordDict)还是会loop很多次

不过像
s = "aabbb"
wordDict = ["a","abbb"]
就会极其的减少loop次数

看看stefan大神的做法:

sentences(i) returns a list of all sentences that can be built from the suffix s[i:].

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        memo = {len(s): ['']}
        def sentences(i):
            if i not in memo:
                memo[i] = [s[i:j] + (tail and ' ' + tail)
                           for j in range(i+1, len(s)+1)
                           if s[i:j] in wordDict
                           for tail in sentences(j)]
            return memo[i]
        return sentences(0)


回到顶部