Leetcode解题-Word Break II

发表于   |   分类于   |  

描述

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

分析

在Word Break的基础上，要求返回所有可能的分词结果。我们用一个二维数组A[i][j]来表示s[j:i]是不是一个单词（注意下标是反的）。然后通过对A进行DFS我们可以还原所有的合法组合。理解了之后要写对还是不容易。

代码

Python

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
class Solution(object):
    def dfs(self, s, A, idx, path, rs):
        if idx == 0:
            rs.append(' '.join(path[::-1]))
            return
        for i in xrange(idx):
            if A[idx][i]:
                # s[i: idx] is a word
                path.append(s[i: idx])
                self.dfs(s, A, i, path, rs)
                path.pop()

    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        A = [[False] * n for i in xrange(n + 1)]
        for i in xrange(1, n + 1):
            for j in xrange(i - 1, -1, -1):
                if dp[j] and s[j: i] in wordDict:
                    dp[i] = True
                    A[i][j] = True
        if not dp[n]:
            return []
        rs = []
        path = []
        self.dfs(s, A, n, path, rs)
        return rs

热评文章