大家好，最近在學習回溯演算法，做到了leetcode的131題，題目如下：
給定一個字串 s，將 s 分割成一些子串，使每個子串都是回文串。
回傳 s 所有可能的分割方案。
示例:
輸入: "aab"
輸出:
[
["aa","b"],
["a","a","b"]
]
我寫了兩種代碼，在我看來這兩種代碼的思路應該是一樣的，都是標準的回溯列舉法。但不知道為什么，第一種做法運行后的結果永遠是回傳空值，第二種倒是可以通過。但就是不知道兩種做法為什么會產生不同的結果（在我看來甚至第一種做法更加標準）。想請教論壇的大神幫忙看看，謝謝幫助！！
第一種做法：
class Solution:
def partition(self, s: str) -> List[List[str]]:
res,ans=[],[]
def backtrack(s):
if len(s)==0:
res.append(ans)
return
for i in range(len(s)):
if s[:i+1]==s[:i+1][::-1]:
ans.append(s[:i+1])
backtrack(s[i+1:])
ans.pop()
backtrack(s)
return res
回傳結果：
輸入: "aab"
輸出:
[
[],
[]
]
第二種做法：
class Solution:
def partition(self, s: str) -> List[List[str]]:
res,ans = [],[]
def back(ans,s):
if len(s) == 0:# 狀態滿足最終要求
res.append(ans) # 加入結果
return
for i in range(0,len(s)):
if s[:i+1]==s[:i+1][::-1]:
back(ans+[s[:i+1]],s[i+1:])
back(ans,s)
return res
輸入: "aab"
輸出:
[
["aa","b"],
["a","a","b"]
]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251123.html