forked from cmhungsteve/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
word-break.py
38 lines (31 loc) · 1 KB
/
word-break.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
# Time: O(n * l^2)
# Space: O(n)
# Given a string s and a dictionary of words dict,
# determine if s can be segmented into a space-separated sequence of one or more dictionary words.
#
# For example, given
# s = "leetcode",
# dict = ["leet", "code"].
#
# Return true because "leetcode" can be segmented as "leet code".
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
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)]
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:
can_break[i] = True
break
return can_break[-1]
if __name__ == "__main__":
print Solution().wordBreak("leetcode", ["leet", "code"])