如何創建一個回傳串列而不超過二維的遞回函式？（Python）

我正在關注YouTube 上的本教程。我正在嘗試創建一個函式，該函式接受兩個輸入，一個目標詞和一個詞庫，并從詞庫回傳一個包含所有可能組合的二維陣列以獲取目標詞。

例如，canConstruct("abc", ["ab", "c", "abc", "d"])應該回傳[["ab","c"],["abc"]]

我的代碼中有很多缺陷，但我現在關注的主要問題是讓最終輸出成為 2d 串列。

我嘗試過以多種方式回傳串列。我認為回傳*list可能會起作用，因為當我列印出來str(*list)似乎洗掉了額外的[]但我不能回傳這個。

以下是相關代碼：

    
    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”不是目標詞這個明顯的問題外，我的回傳串列是['a',['ab']]它應該是什么時候[['a', 'ab']]。

我認為問題可能出在，way.insert(0, word)但我真的不太確定，因為我自己有點困惑。

任何關于如何將串列傳回遞回函式以使其不會變得混亂的建議將不勝感激！

uj5u.com熱心網友回復：

有這些問題：

• result不應該是全域變數，因為您從遞回呼叫中獲得結果，然后將其合并回result. 這將導致重復資訊。此外，whenresult是全域的，你有一個帶有副作用的函式，呼叫者應該result在它想要進行新呼叫時重置。這是不好的做法。

  取而代之result的是一個本地名稱，它[]在函式的開頭設定為，并回傳給呼叫者。

• 您不希望append得到遞回呼叫的結果，因為該結果與您構建的結果具有相同的 2D 結構。所以你需要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

uj5u.com熱心網友回復：

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

標籤：Python 列表 递归 动态的

上一篇：Prolog-檢查第二個串列是否包含第一個串列中的所有偶數

下一篇：矩陣行列式