-
Notifications
You must be signed in to change notification settings - Fork 3
/
word-break-problem.py
91 lines (64 loc) · 1.77 KB
/
word-break-problem.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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# Python3 implementation to break
# a sequence into the words of
# the dictionary
# Unordered_map used for storing
# the sentences the key string
# can be broken into
mp = {}
# Unordered_set used
# to store the dictionary.
dict_t = set()
# Utility funtion used for
# printing the obtained result
def printResult(A):
for i in range(len(A)):
print(A[i])
# Utility function for
# appending new words
# to already existing strings
def combine(prev, word):
# Loop to find the append string
# which can be broken into
for i in range(len(prev)):
prev[i] += " " + word
return prev
# Utility funtion for word Break
def wordBreakUtil(s):
# Condition to check if the
# subproblem is already computed
if s in mp:
return mp[s]
res = []
# If the whole word is a dictionary
# word then directly append into
# the result array for the string
if s in dict_t:
res.append(s)
# Loop to iterate over the substring
for i in range(1, len(s)):
word = s[i:]
# If the substring is present into
# the dictionary then recurse for
# other substring of the string
if word in dict_t:
rem = s[:i]
prev = combine(wordBreakUtil(rem), word)
for i in prev:
res.append(i)
# Store the subproblem
# into the map
mp[s] = res
return res
# Master wordBreak function converts
# the string vector to unordered_set
def wordBreak(s, wordDict):
# Clear the previous stored data
mp.clear()
dict_t.clear()
for i in wordDict:
dict_t.add(i)
return wordBreakUtil(s)
# Driver Code
if __name__ == "__main__":
wordDict1 = ["cat", "cats", "and", "sand", "dog"]
printResult(wordBreak("catsanddog", wordDict1))