0

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"]))  
                                      

0 Answers0