Python-Rekursion und Umfang der Variablen

Question

Ich versuche, die Lösung für dieses LeetCode-Problem Palindrome Partitioning herauszufinden. Dies ist, was ich derzeit haben:

def partition(s): 
    out = [] 
    def isPalindrome(word): 
     return word == word[::-1] 

    def addPalindrome(word, start, partition): 
     if start == len(word): 
      out.append(partition) #where I append to 'out' 
      print out, partition # where I print the finished partition 
      return 
     for i in range(start+1, len(word)+1): 
      sub = word[start:i] 
      if isPalindrome(sub): 
       partition.append(sub) 
       addPalindrome(word, i, partition) 
       partition.pop() 

    if not s: 
     return [] 
    addPalindrome(s, 0, []) 
    return out 

print partition('aaa') 

Die richtige Lösung mit dem Eingang ‚aaa‘ ist [['a', 'a', 'a'], ['a', 'aa'], ['aa', 'a'], ['aaa']]. Wenn ich partition im Basisfall drucke, scheint es richtig zu sein. Ich angehängt sie an eine out Variable, die außerhalb des Umfangs der Rekursion sein sollte und korrekt zurückgeben.

Dies ist jedoch nicht der Fall. Ich verstehe nicht, warum out im Basisfall Druck würde in dieser Folge:

[['a', 'a', 'a']] 
[['a', 'aa'], ['a', 'aa']] 
[['aa', 'a'], ['aa', 'a'], ['aa', 'a']] 
[['aaa'], ['aaa'], ['aaa'], ['aaa']] 

Schließlich wenn out Rückkehr scheint es leere Arrays zurück. Was ist denn hier los?

Der Ausgang von out nach Rekursion ist [[], [], [], []].

Dies ist python2.7

Answer 1

Die Fragen, die ich sehe, sind 1) die Erinnerung auf Speicher kopieren (wie in den Kommentaren erwähnt) und 2) die Verwendung eines globalen vielmehr das wachsende Ergebnis zu retten, als die Handhabung das innerhalb der Rekursion. Lassen Sie den Code vereinfachen und beiden Probleme beheben:

def isPalindrome(word): 
    return word == word[::-1] 

def addPalindrome(word, start, partitions): 
    result = [] 

    if start == len(word): 
     result.append(list(partitions)) # where I append to 'out' 
    else: 
     for i in range(start+1, len(word)+1): 
      sub = word[start:i] 

      if isPalindrome(sub): 
       partitions.append(sub) 
       result.extend(addPalindrome(word, i, partitions)) 
       partitions.pop() 
    return result 

def partition(s): 
    out = [] 

    if s: 
     out = addPalindrome(s, 0, []) 

    return out 

print partition('aaa') 

Wenn innerhalb der Rekursion das Ergebnis reicht, und nicht als global, ist der Schlüssel zu wissen, wann zu *.append() und wenn das wachsenden Ergebnis *.extend().