forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
word-break-ii.py
56 lines (49 loc) · 1.68 KB
/
word-break-ii.py
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# Time: O(n * l^2 + n * r), l is the max length of the words,
# r is the number of the results.
# Space: O(n^2)
#
# 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"].
#
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
n = len(s)
max_len = 0
for string in wordDict:
max_len = max(max_len, len(string))
can_break = [False for _ in xrange(n + 1)]
valid = [[False] * n for _ in xrange(n)]
can_break[0] = True
for i in xrange(1, n + 1):
for l in xrange(1, min(i, max_len) + 1):
if can_break[i-l] and s[i-l:i] in wordDict:
valid[i-l][i-1] = True
can_break[i] = True
result = []
if can_break[-1]:
self.wordBreakHelper(s, valid, 0, [], result)
return result
def wordBreakHelper(self, s, valid, start, path, result):
if start == len(s):
result.append(" ".join(path))
return
for i in xrange(start, len(s)):
if valid[start][i]:
path += [s[start:i+1]]
self.wordBreakHelper(s, valid, i + 1, path, result)
path.pop()
if __name__ == "__main__":
print Solution().wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"])