如何创建一个 returns 列表的递归函数，而不会超过二维？ (Python)

Question

我正在关注 YouTube 上的 this 教程。我正在尝试创建一个函数，它接受两个输入，一个目标词和一组词，以及 returns 一个二维数组，其中包含词库中所有可能的组合以到达目标词。

例如，canConstruct("abc", ["ab", "c", "abc", "d"])应该return[["ab","c"],["abc"]]

我的代码有很多缺陷，但我现在关注的主要问题是让最终输出成为一个二维列表。

我已经尝试 return 以多种方式返回列表。我认为 returning *list 可能会工作，因为当我打印出 str(*list) 时似乎删除了额外的 [] 但我不能 return 这个。

相关代码如下：

    
    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

我已经使我的测试用例变得超级简单，这样我就可以更好地理解错误检查打印语句。下面是我传递给函数的内容：

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

输出是这样的：

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']], [...]]

除了“aab”不是目标词这一明显问题外，我的 returning 列表是 ['a',['ab']]，而它应该是 [['a', 'ab']]。

我认为问题可能出在 way.insert(0, word)，但我真的不太确定，因为我把自己弄糊涂了。

任何关于如何在递归函数中传回列表以免它变得一团糟的建议，我们将不胜感激！

Answer 1

存在这些问题：

result 不应该是一个全局变量，因为你从递归调用中得到一个结果，然后将它合并回 result。这将导致重复信息。此外，当 result 是全局的时，你有一个有副作用的函数，调用者应该在想要进行新调用时重置 result 。这是不好的做法。

而是让 result 成为一个 local 名称，它在函数开始时设置为 []，并返回给调用者。
您不想 append 递归调用的结果，因为该结果与您的结果具有相同二维结构建造。所以你需要使用 extend 来代替。
不是你的问题，但是 memo = {} 作为默认值参数是个坏主意。而是让默认值为 None，并在函数体内分配空字典。否则该函数的下一次调用将继续使用先前填充的备忘录，这是不希望的。

这里更正：

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

Answer 2

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

如何创建一个 returns 列表的递归函数，而不会超过二维？ (Python)

How can I create a recursive function that returns a list without it becoming more than two dimension? (Python)

python

list

recursion

dynamic