why using a dictionary in a recursion leads to mistakes-python?-CodePudding

I want to make a program in python where you give a target word and an array of words and check if it possible to make the target word using the words from the array. Also I want to return all the possible ways.

def allConstruct(target,wordBank):   
    if target=='': return [[]]
    can=[]
    for word in wordBank:
        if target.find(word)==0 :
            suffix=target[len(word):]
            suffixways=allConstruct(suffix,wordBank)
            for lis in suffixways:
                lis.insert(0,word)
            can.extend(suffixways)
    return can
print(allConstruct('purple',['purp','p','ur','le','purpl']))

If you run this program you get [['purp', 'le'], ['p', 'ur', 'p', 'le']] which is correct. Now trying to make it more efficient, I introduce a dictionary.

def allConstruct(target,wordBank, memo=None):    
    if memo is None: memo={}
    if target in memo: return memo[target]
    if target=='': return [[]]

    can=[]
    for word in wordBank:
        if target.find(word)==0 :
            suffix=target[len(word):]
            suffixways=allConstruct(suffix,wordBank,memo)
            for lis in suffixways:
                lis.insert(0,word)
            can.extend(suffixways)
    memo[target]=can

    return can
print(allConstruct('purple',['purp','p','ur','le','purpl']))

The result here is [['p', 'ur', 'p', 'purp', 'le'], ['p', 'ur', 'p', 'purp', 'le']]. In fact, the memo at the first step is {'le': [['le']]} and then it becomes {'le': [['p', 'purp', 'le']], 'ple': [['p', 'purp', 'le']]}. I do not understand why the value for 'le' changes as the program runs. Can you help me undertand this? Thank you very much!

CodePudding user response：

Your problem is due to the fact that you are adding lists to memo that you then go on and modify. Look at the end of your function. You set memo[target]=can and then you return can. But now look at what happens in the calling version of the function. It assigns the result of the inner call to the variable suffixways and then goes on and modifies the values in that list. You don't want to do that. You need to put values into memo that aren't going to change. You can do that with copy.deepcopy()

import copy

def allConstruct(target,wordBank, memo=None):
    if memo is None: memo={}
    if target in memo: return memo[target]
    if target=='': return [[]]

    can=[]
    for word in wordBank:
        if target.find(word)==0:
            suffix=target[len(word):]
            suffixways=allConstruct(suffix,wordBank,memo)
            for lis in suffixways:
                lis.insert(0,word)
            can.extend(suffixways)
    memo[target]=copy.deepcopy(can)
    return can

print(allConstruct('purple',['purp','p','ur','le','purpl']))

Result:

[['purp', 'le'], ['p', 'ur', 'p', 'le']]

This is the same result as what you get with your first version.