leetCode131求教
来源：8-2 什么是回溯
qq_山上山_0
2022-04-01
波波老司，很久不见; 想shi你了(在看你的机器学习；学不动了回来做题)
结果是[[],[]]
python3
class Solution:
res = []
word = []
def huiwei(self, s):
if len(s) == '':
return False
if len(s) == 1:
return True
for i in range(int(len(s) / 2)):
if s[i] != s[len(s) - 1 - i]:
return False
return True
def dfs(self, s, index):
if self.word != [] and ''.join(self.word) == s:
self.res.append(self.word)
return
for i in range(1, len(s)):
if index + i > len(s):
return
if self.huiwei(s[index:index + i]):
self.word.append(s[index:index + i])
self.dfs(s, index + i)
self.word.pop(len(self.word) - 1)
return
def partition(self, s: str) :
self.word = []
self.res = []
self.dfs(s, 0)
return self.res
写回答
1回答
-
你的代码的主要问题是：每次递归到底以后，加入到 res 中的是 self.word。也就是加入到 res 中的是 word 这个 list 的引用。回到上一层回溯的时候，对 word 的改变，也将改变 res 中已经添加的所有元素。
修改成每次添加一个 word 的副本即可。即：self.res.append(self.word[:])
但是你的代码还有其他的 bug，修改完这个问题，你可以再调试跟踪一下？
以下代码是可以 ac 的：
class Solution: res = [] word = [] def huiwei(self, s): return s == s[::-1] def dfs(self, s, index): if self.word != [] and ''.join(self.word) == s: self.res.append(self.word[:]) return for i in range(1, len(s) + 1): if index + i > len(s): return if self.huiwei(s[index:index + i]): self.word.append(s[index:index + i]) self.dfs(s, index + i) self.word.pop() return def partition(self, s: str) : self.word = [] self.res = [] self.dfs(s, 0) return self.res
继续加油！：）
052022-04-02
相似问题
leetcode37. 数独求教
回答 1
LeetCode130求教
回答 1
LeetCode120，求教
回答 1
LeetCode 63 求教
回答 1
波波老师求教word search2
回答 2