给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串
#错误写法
def partition(s):
def huiwen(temp):
"""判断是否是回文串"""
return temp == temp[::-1]
def backtracking(s_temp, result, temp_result):
if not s_temp:
# 已经走到最后一个字符
result.append(temp_result)
return
for i in range(1, len(s_temp) + 1): # start位置横向找第二刀
if huiwen(s_temp[:i]):
temp_result.append(s_temp[:i])
backtracking(s_temp[i:], result, temp_result)
result = []
backtracking(s, result, [])
return result
#第一种写法
def partition(s):
def huiwen(temp):
"""判断是否是回文串"""
return temp == temp[::-1]
def backtracking(s_temp, result, temp_result):
if not s_temp:
# 已经走到最后一个字符
result.append(temp_result[:])
return
for i in range(1, len(s_temp) + 1):
if huiwen(s_temp[:i]):
temp_result.append(s_temp[:i])
backtracking(s_temp[i:], result, temp_result)
temp_result.pop()
result = []
backtracking(s, result, [])
return result
#第二种写法
def partition(s):
def huiwen(temp):
"""判断是否是回文串"""
return temp == temp[::-1]
def backtracking(s_temp, result, temp_result):
if not s_temp:
# 已经走到最后一个字符
result.append(temp_result)
return
for i in range(1, len(s_temp) + 1):
if huiwen(s_temp[:i]):
backtracking(s_temp[i:], result, temp_result+[s_temp[:i]])
result = []
backtracking(s, result, [])
return result
#LeetCode上
class Solution:
def _huiwen(self, temp):
"""判断是否是回文串"""
return temp == temp[::-1]
def backtrack(self, s_temp, res, path):
if not s_temp:
res.append(path) # 类你面的path却没有这个问题
return
for i in range(1, len(s_temp) + 1): # 注意起始和结束位置
if self._huiwen(s_temp[:i]):
self.backtrack(s_temp[i:], res, path + [s_temp[:i]])
def partition(self, s):
res = []
self.backtrack(s, res, [])
return res
if __name__ == '__main__':
print(partition("cdd"))
f = Solution()
res = f.partition("cdd")
print(res)
产生错误的原因：可变类型变量的引用，不具备深copy
以下代码尝试了python中的常见类型引用的常见情况
p1 = "abc"
p2 = 123
p3 = 12.12
p4 = (1, 2)
p5 = [1, 2, 3]
p6 = {"w1": 1, "w2": 2}
p7 = {1, 2, 3, 4}
class A():
def __init__(self, name):
self.name = name
def __repr__(self):
return self.name
p8 = A("haha")
print("#" * 100)
print("(1)基础的不可变string，int, float, tuple的类型变量")
print("赋值string类型变量")
temp_p1 = p1
print(temp_p1, p1)
p1 = "abc1"
print(temp_p1, p1)
print("赋值int类型变量")
temp_p2 = p2
print(temp_p2, p2)
p2 = 1234
print(temp_p2, p2)
print("赋值float类型变量")
temp_p3 = p3
print(temp_p3, p3)
p3 = 1234.12
print(temp_p3, p3)
print("赋值tuple类型变量")
temp_p4 = p4
print(temp_p4, p4)
p4 += (3, 4)
print(temp_p4, p4)
print("list变量由基础类型组成")
temp_p5 = [p1, p2, p3, p4]
print(temp_p5, p1, p2, p3, p4)
p1, p2, p3, p4 = "1", 1, 1.1, (1, 1)
print(temp_p5, p1, p2, p3, p4)
print("dict变量由基础类型组成")
temp_p6 = {}
temp_p6 = {"w1": p1, "w2": p2, "w3": p3, "w4": p4}
print(temp_p6, p1, p2, p3, p4)
p1, p2, p3, p4 = "2", 2, 2.2, (2, 2)
print(temp_p6, p1, p2, p3, p4)
print("set变量由基础类型组成")
temp_p7 = {}
temp_p7 = {p1, p2, p3, p4}
print(temp_p7, p1, p2, p3, p4)
p1, p2, p3, p4 = "3", 3, 3.3, (3, 3)
print(temp_p7, p1, p2, p3, p4)
print("#" * 100)
print("(2)可变的list类型变量")
print("赋值=")
temp_p8 = p5
print(temp_p8, p5)
p5.append(4)
print(temp_p8, p5)
p5.extend([5])
print(temp_p8, p5)
p5 += [6]
print(temp_p8, p5)
p5 = [1, 2]
print(temp_p8, p5)
print("装入list")
temp_p9 = []
temp_p9.append(p5)
print(temp_p9, p5)
p5.append(3)
print(temp_p9, p5)
p5 += [4]
print(temp_p9, p5)
print("切片装入list")
temp_p10 = []
temp_p10.append(p5[:])
print(temp_p10, p5)
p5.append(5)
print(temp_p10, p5)
p5 += [6]
print(temp_p10, p5)
print("装入dict")
temp_p11 = {}
temp_p11["w1"] = p5
print(temp_p11, p5)
p5.pop()
print(temp_p11, p5)
p5 += [6]
print(temp_p11, p5)
print("切片装入dict")
temp_p12 = {}
temp_p12["w1"] = p5[:]
print(temp_p12, p5)
p5.pop()
print(temp_p12, p5)
p5 += [6]
print(temp_p12, p5)
print("#" * 100)
print("(3)可变的dict类型变量")
print("赋值=")
temp_p13 = p6
print(temp_p13, p6)
p6["w3"] = 3
print(temp_p13, p6)
p6 = {"f": "f"}
print(temp_p13, p6)
print("装入list")
temp_p14 = []
temp_p14.append(p6)
print(temp_p14, p6)
p6["w4"] = 4
print(temp_p14, p6)
print("装入dict")
p6 = {"w1": 1, "w2": 2}
temp_p15 = {}
temp_p15["w1"] = p6
print(temp_p15, p6)
p6.pop("w1")
print(temp_p15, p6)
print("#" * 100)
print("(4)可变的set类型变量")
print("赋值=")
temp_p16 = p7
print(temp_p16, p7)
p7.pop()
print(temp_p16, p7)
p7 = {1, 2}
print(temp_p16, p7)
print("装入list")
temp_p17 = []
temp_p17.append(p7)
print(temp_p17, p7)
p7.add(1)
print(temp_p17, p7)
print("装入dict")
temp_p18 = {}
temp_p18["w1"] = p7
print(temp_p18, p7)
p7.pop()
print(temp_p18, p7)
print("#" * 100)
print("(5)可变的自定义类变量")
print("赋值=")
temp_p19 = p8
print(temp_p19, p8)
p8.name = "123"
print(temp_p19, p8)
print("装入list")
temp_p20 = []
temp_p20.append(p8)
print(temp_p20, p8)
p8.name = "temp_p20"
print(temp_p20, p8)
print("装入dict")
temp_p21 = {}
temp_p21["w1"] = p8
print(temp_p21, p8)
p8.name = "temp_p21"
print(temp_p21, p8)
2、139. 单词拆分
def wordBreak(s, wordDict):
"""回溯方法+记忆化"""
def _backtracking(start_index, memory):
if start_index >= len(s):
return True
if memory[start_index] != -1:
return memory[start_index]
for i in range(start_index + 1, len(s) + 1):
if s[start_index:i] in wordDict and _backtracking(i, memory):
memory[start_index] = 1
return True
memory[start_index] = 0
return False
memory = [-1] * len(s) # 记录每个位置作为起始位置的计算结果，减少重复计算的次数
return _backtracking(0, memory)
