I am following this tutorial on YouTube. I am trying to create a function that takes two inputs, a target word and a bank of words, and returns a 2d array of all possible combinations from the word bank to get to the target word.

For example, canConstruct("abc", ["ab", "c", "abc", "d"]) should return [["ab","c"],["abc"]]

There are quite a few flaw in my code, but the main one I am focusing on now is getting the final output to be a 2d list.

I have tried returning the list back in multiple ways. I thought returning *list might work as when I print out str(*list) is seems to remove the extra [] but I can't return this.

Here is the relevant code:

    
    result = []

    def allConstruct(target, wordBank, memo = {}):
        if target == "":
            return([[]])
    
        if target in memo:
            return memo[target]
    
        for word in wordBank:

            ...

            # if match never gets set to False, that means word is a subset of target
            if match == True:
                #remove word from beginning of target
                new_target = target[word_len:]
                suffix_ways = allConstruct(new_target, wordBank)
                for way in suffix_ways:
                    print("inserting word: "   word   " at start of list: "   str(way))
                    way.insert(0, word) 
                    print("The result is "   str(way))
                result.append(suffix_ways)
                memo[target] = result
    
        memo[target] = result
        return result

I have made my test case super simple so I can better understand the error checking print statements. Below is what I pass into the function:

result = allConstruct("ab", ["ab", "a"])
print(result)

The output is this:

inserting word: ab at start of list: []
The result is ['ab']
inserting word: a at start of list: [['ab']]
The result is ['a', ['ab']]
[['a', ['ab']], [...]]

Apart from the glaring issue that "aab" is not the target word, my returning list is ['a',['ab']] when it should be [['a', 'ab']].

I think the issue might be at way.insert(0, word) but I'm really not too sure as I've confused myself quite a bit.

Any advice on how to pass a list back in a recursive function so it doesn't become a mess would be greatly appreciated!

CodePudding user response：

There are these issues:

• result should not be a global variable, because you get a result from the recursive call, and you merge that back into result. This will lead to duplicate information. Moreover, when result is global, you have a function with side effects, and the caller should reset result whenever it wants to make a new call. This is bad practice.

  Instead let result be a local name, which is set to [] at the start of the function, and is returned to the caller.

• You don't want to append the result from the recursive call, since that result has the same 2D structure as the one you build. So you need to use extend instead.

• Not your issue, but memo = {} as default valued parameter is a bad idea. Instead let the default value be None, and assign the empty dictionary inside the body of the function. Otherwise a next call of the function will keep using the previously populated memo, which is undesired.

Here is a correction:

def allConstruct(target, wordBank, memo = None):
    if not memo:
        memo = {}  # Initialise for *every* toplevel call
    result = []  # Local!

    if target == "":
        return [[]]

    if target in memo:
        return memo[target]

    for word in wordBank:
        word_len = len(word)
        match = target.startswith(word)

        # if match never gets set to False, that means word is a subset of target
        if match == True:
            # Remove word from beginning of target
            new_target = target[word_len:]
            suffix_ways = allConstruct(new_target, wordBank)
            for way in suffix_ways:
                print("inserting word: "   word   " at start of list: "   str(way))
                way.insert(0, word) 
                print("The result is "   str(way))
            result.extend(suffix_ways)  # Extend!
            memo[target] = result

    memo[target] = result
    return result

CodePudding user response：

def allConstruct(target, wordBank):
new_res=[]
result = []  # Local!
memo=None
if not memo:
    memo = {}  # Initialise for *every* toplevel call

if target == "":
    return [[]]

if target in memo:
    return memo[target]

for word in wordBank:
    word_len = len(word)
    match = target.startswith(word)

    # if match never gets set to False, that means word is a subset of target
    if match == True:
        # Remove word from beginning of target
        new_target = target[word_len:]
        suffix_ways = allConstruct(new_target, wordBank)
        for way in suffix_ways:
            print("inserting word: "   word   " at start of list: "   str(way))
            way.insert(0, word)
            print("The result is "   str(way))
            new_res.append(way)
print(new_res)
return new_res