Python class 变量在方法结束后因未将 deepcopy 应用于列表而发生更改

Question

试图使用回溯解决 python 中的这个 leetcode 问题 -

Given a string s, partition s such that every substring of the partition is a palindrome. 
Return all possible palindrome partitioning of s.

此解决方案的输出很奇怪 -

class Solution:
    
    a = list()

    def backtrack(self, start, string, palindrome, stack):

        if start == len(string):
            self.a.append(stack)
            return
        if start == len(string)-1:
            stack.append(string[start])
            self.a.append(stack)
            stack.pop()
            return

        for end in range(start, len(string)):
            if start == end:
                stack.append(string[start])
                self.backtrack(start+1, string, palindrome, stack)
                stack.pop()

            elif string[start] == string[end] and ((end == start+1) or palindrome[start+1][end-1]):
                stack.append(string[start:end+1])
                palindrome[start][end] = True
                self.backtrack(end+1, string, palindrome, stack)
                stack.pop()

    def partition(self, string):
        stack =  []
        self.a.clear()
        palindrome = [[False for __ in range(len(string))] for _ in range(len(string))]
        for i in range(len(string)):
            palindrome[i][i] = True
        self.backtrack(0, string, palindrome, stack)
        return self.a

输入：aab

输出：

[[],[]]

此代码有效，只是将 list 更改为 set 并进行了其他小改动

class Solution:
    
    a = set()

    def backtrack(self, start, string, palindrome, stack):

        if start == len(string):
            if ",".join(stack) not in self.a:
                self.a.add(",".join(stack))
            return
        if start == len(string)-1:
            stack.append(string[start])
            if ",".join(stack) not in self.a:
                self.a.add(",".join(stack))
            stack.pop()
            return

        for end in range(start, len(string)):
            if start == end:
                stack.append(string[start])
                self.backtrack(start+1, string, palindrome, stack)
                stack.pop()

            elif string[start] == string[end] and ((end == start+1) or palindrome[start+1][end-1]):
                stack.append(string[start:end+1])
                palindrome[start][end] = True
                self.backtrack(end+1, string, palindrome, stack)
                stack.pop()

    def partition(self, string):
        stack = answer = []
        palindrome = [[False for __ in range(len(string))] for _ in range(len(string))]
        for i in range(len(string)):
            palindrome[i][i] = True
        self.backtrack(0, string, palindrome, stack)
        ans = [item.split(",") for item in self.a]
        self.a.clear()
        return ans

输入：aab

输出：[["a","a","b"],["aa","b"]]

问题：https://leetcode.com/problems/palindrome-partitioning/

Answer 1

想通了！我必须在第一个代码中附加 stack 时应用 copy.deepcopy。

from copy import deepcopy

a = list()

def backtrack(self, start, string, palindrome, stack):

    if start == len(string):
        dc = deepcopy(stack)
        self.a.append(dc)
        return
    if start == len(string)-1:
        stack.append(string[start])
        dc = deepcopy(stack)
        self.a.append(dc)
        stack.pop()
        return

在 python 中，列表的副本并不总是生成新对象。例如-

>>> l=[1,2,3,4]
>>> x = l
>>> del l[1]
>>> l
[1, 3, 4]
>>> x
[1, 3, 4]

在上面的代码中，x and l指向同一个列表

使用 copy.deepcopy 时，会创建一个新列表 -

>>> from copy import deepcopy
>>> l=[1,2,3,4]
>>> x = deepcopy(l)
>>> del l[1]
>>> l
[1, 3, 4]
>>> x
[1, 2, 3, 4]

Answer 2

下面是类似的深度优先搜索解决方案，语句较少：

class Solution:
    def partition(self, s):
        res = []
        self.depth_first_search(s, [], res)
        return res

    def depth_first_search(self, s, path, res):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1):
            if self.is_palindrome(s[:i]):
                self.depth_first_search(s[i:], path + [s[:i]], res)

    def is_palindrome(self, s):
        return s == s[::-1]


print(Solution().partition("aab"))

Python class 变量在方法结束后因未将 deepcopy 应用于列表而发生更改

Python class variable getting changed after method ends for not applying deepcopy to list

python

algorithm

backtracking