Присоединение к списку против конкатенации в рекурсивных вызовах Python - PullRequest
2 голосов
/ 07 ноября 2019

Пожалуйста, посмотрите на следующую проблему Leetcode: https://leetcode.com/problems/generate-parentheses/

В ней вы пытаетесь создать серию скобок с парой правил, как должен выглядеть каждый список скобок.

Мне известны два подхода, которые кажутся мне функционально идентичными, но работает только один. Я понимаю, что append возвращает None и изменяет на месте, но я не вижу, как это влияет на рекурсивный процесс.

Вот код, который не работает:

class Solution:
    def generate(self, output, temp, n):
            if len(temp) == 2*n:
                output.append(temp)
            left_count = temp.count("(")
            right_count = temp.count(")")
            if left_count < right_count:
                return
            if left_count < n:
                self.generate(output, temp.append("("), n)
            if left_count > right_count:
                self.generate(output, temp.append(")"), n)


    def generateParenthesis(self, n: int) -> List[str]:      
        output = []
        self.generate(output, ["("], n)
        return output

Этокод (с использованием concat) работает:

class Solution:
    def generate(self, output, temp, n):
            if len(temp) == 2*n:
                output.append(temp)

            left_count = temp.count("(")
            right_count = temp.count(")")
            if left_count < right_count:
                return
            if left_count < n:
                self.generate(output, temp + "(", n)
            if left_count > right_count:
                self.generate(output, temp + ")", n)

    def generateParenthesis(self, n: int) -> List[str]:      
        output = []
        self.generate(output, "", n)
        return output

Может кто-нибудь уточнить, что я здесь скучаю? Большое спасибо.

1 Ответ

1 голос
/ 07 ноября 2019

.append возвращает None вместо добавленного списка, как и следовало ожидать. Сначала вы хотите добавить круглые скобки в temp, а затем использовать «обновленный» temp в качестве аргумента.

class Solution:
    def generate(self, output, temp, n):
            if len(temp) == 2*n:
                output.append(temp)

            left_count = temp.count("(")
            right_count = temp.count(")")
            if left_count < right_count:
                return
            if left_count < n:
                temp.append("(") # does not return anything but modifies temp.
                self.generate(output, temp, n)
            if left_count > right_count:
                temp.append(")") # same.
                self.generate(output, temp, n)


    def generateParenthesis(self, n: int) -> List[str]:      
        output = []
        self.generate(output, ["("], n)
        return output
...