-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathcount_construct.py
130 lines (109 loc) · 4.06 KB
/
count_construct.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
"""
Problem Statement:
Write a function countConstruct(target, wordBank) that accepts a target string and an array of strings.
The function should return the number of ways that the target can be constructed
by concatenating elements of the wordbank array.
You may reuse elements of 'wordbank' as many times as needed.
canConstruct("", ["any"]) -> 0
canConstruct("abcde", ["ab", "c", "cde"]) -> 1
Hints for time complexity:
Considering target is of length M and number of elements is N in wordBank
the worst case will be when words in wordBank is of length 1
so the height of the tree will be M
for every node there will be N branches.
"""
from functools import lru_cache, partial
from utils.decorators import time_this
class CountConstruct:
def __init__(self, target, wordbank):
self.solutions = {
"recursive": partial(self.recursive, target, wordbank),
"dynamic_programming": partial(self.dp, target, wordbank),
"dp_lru_cache": partial(self.dp_lru_cache, target, tuple(wordbank)),
"dp_tabulation": partial(self.dp_tabulation, target, wordbank)
}
@staticmethod
def recursive(target, wordbank):
"""
Time complexity: O(N^M*M) M for finding string
Space Complexity: O(M^2) M Due to call stack and
M due to storing a string of len M (worstcase) for every call
"""
if target == "":
return 1
count = 0
for word in wordbank:
if target.find(word) == 0:
updated_target = target[len(word):]
count += CountConstruct.recursive(updated_target, wordbank)
# print(count, updated_target)
return count
@staticmethod
def dp(target, wordbank, memo=None):
"""
Time complexity: O(N*M^2)
Space Complexity: O(M*2)
"""
if memo is None:
memo = {}
val = memo.get(target)
if val is not None:
return val
if target == "":
return 1
count = 0
for word in wordbank:
if target.find(word) == 0:
updated_target = target[len(word):]
count += CountConstruct.dp(updated_target, wordbank, memo)
memo[target] = count
return count
@staticmethod
@lru_cache
def dp_lru_cache(target, wordbank):
"""
Time complexity: O(N*M^2)
Space Complexity: O(M^2)
"""
if target == "":
return 1
count = 0
for word in wordbank:
if target.find(word) == 0:
updated_target = target[len(word):]
count += CountConstruct.dp_lru_cache(updated_target, wordbank)
return count
@staticmethod
def dp_tabulation(target, wordbank):
"""
Time complexity: O(N*M^2)
Space Complexity: O(M)
"""
table = [0]*(len(target)+1)
table[0] = 1
for i in range(len(target)+1):
if table[i]:
for word in wordbank:
if target[i:i+len(word)] == word:
next_place = i + len(word)
if next_place <= len(target):
table[next_place] += table[i]
# print(target[:i], word, table[next_place])
# print(table)
return table[len(target)]
@staticmethod
@time_this()
def run(func):
print(f"Solution: {func()}")
def execute_all(self):
print("\nSolutions to CountConstruct\n")
for name, solution in self.solutions.items():
print(f'Algo-Name: {name} {" -" * 90}')
self.run(solution)
print('-' * 100)
CountConstruct("", ["any"]).execute_all()
CountConstruct("abcde", ["ab", "c", "cde", "de"]).execute_all()
CountConstruct("purple", ["purp", "purpl", "le", "p", "ur"]).execute_all()
# CountConstruct("kuchbhi", ["ha", "he", "hu", "bhi"]).execute_all()
# CountConstruct("qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqe",
# ["q", "qq", "qqq", "qqqq", "qqqqq", "qqqqqq"]).execute_all()