I have these two codes: for finding all the ways we can construct the target string using wordBank. I am currently learning memoization. The second code is giving wrong answers, seems like memo is becoming common for different calls as given in last code section.
def all_construct(target, word_bank):
memo = {}
def helper(target, word_bank):
if target == "":
return [[]]
if target in memo:
return memo[target]
result = []
for word in word_bank:
if len(target) >= len(word) and target[: len(word)] == word:
suffix = target[len(word) :]
suffix_ways = helper(suffix, word_bank)
target_ways = [[word] + way for way in suffix_ways]
if target_ways:
result.extend(target_ways)
memo[target] = result
return result
return helper(target, word_bank)
And
def allConstruct(target, wordBank, memo = {}):
if target in memo : return memo[target]
if target == "": return [[]]
totalWays = []
for x in wordBank:
if target[:len(x)] == x:
remainderWays = allConstruct(target[len(x):], wordBank, memo)
for y in remainderWays:
y.insert(0, x)
totalWays += remainderWays
memo[target] = totalWays
return totalWays
Calls:
print(all_construct("purple", ["purp", "p", "ur", "le", "purpl"]))
print(all_construct("abcdef", ["ab", "abc", "cd", "def", "abcd","ef"]))
print(all_construct("enterapotentpot", ["a", "p", "ent", "enter", "ot", "o", "t"]))
print(all_construct("eeeeeeeeeeef", ["e", "ee", "eee", "eeee", "eeeee", "eeeeee"]))