我想在 python 中制作一個程式，在其中給出一個目標詞和一個詞陣列，并檢查是否可以使用陣列中的詞來制作目標詞。我也想回傳所有可能的方式。
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']))
如果你運行這個程式，你會得到 [['purp', 'le'], ['p', 'ur', 'p', 'le']] 這是正確的。現在為了提高效率，我介紹了一本字典。
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']))
這里的結果是 [['p', 'ur', 'p', 'purp', 'le'], ['p', 'ur', 'p', 'purp', 'le']]。其實第一步的備忘錄是 {'le': [['le']]} 然后變成了 {'le': [['p', 'purp', 'le']], 'ple '：[['p'，'purp'，'le']]}。我不明白為什么“le”的值會隨著程式的運行而改變。你能幫我理解這個嗎？非常感謝！
uj5u.com熱心網友回復：
您的問題是由于您要添加串列memo然后繼續修改。查看函式的結尾。你設定memo[target]=can然后你回傳can。但是現在看看函式的呼叫版本會發生什么。它將內部呼叫的結果分配給變數suffixways，然后繼續修改該串列中的值。你不想那樣做。memo您需要將不會改變的值放入其中。你可以這樣做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']))
結果：
[['purp', 'le'], ['p', 'ur', 'p', 'le']]
這與您使用第一個版本獲得的結果相同。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/515671.html
標籤：Python功能字典递归