pydata

Keep Looking, Don't Settle

leetcode 140. Word Break II

140. Word Break II是一道难度为hard的题,不太好写。

题目大意:单词分割,给定一个字符串和一个字典,如果字符串能由字典里的单词组成,那么返回组成的单词。最后要求返回所有的可能的解。

139. Word Break不同的是,这道题要找到解,而且要找出所有的解。

动态规划

对每个分割点,如果右边在字典里,同时如果左边有解,那么这个分割有效

对左边采取同样的办法,先分割成左右,然后看右边是不是在字典里,在的话再检查左边

如此迭代下去

注意的是左边可能不止一个分割办法,最要要把右边跟左边的所有可能解加在一起,这样才能找到所有的解

def wordBreak(self, s, wordDict):
    self.mem_ = {}

    def dfs(s, wordDict):
        if s in self.mem_:
            return self.mem_[s]
        ans = [] # answer for curr s
        if s in wordDict:
            ans.append(s)
        for j in range(1, len(s)):
            right = s[j:]
            if right not in wordDict:
                continue
            left = s[:j]
            left_ans = [x + ' ' + right for x in dfs(left, wordDict)]
            ans += left_ans
        self.mem_[s] = ans
        return self.mem_[s]
    return dfs(s, wordDict)

Solution().wordBreak("catsanddog", ['cat', 'cats', 'and', 'sand', 'dog'])