代码随想录算法训练营第二十六天(回溯算法篇)|131. 分割回文串
2023-12-19 06:10:34
131. 分割回文串
题目链接:131. 分割回文串 - 力扣(LeetCode)
思路
分割字串和组合的题目有异曲同工之妙。
组合:选好数组中第一个数,接着选数组中第一个后面的数,进入递归。第一个树层代表选的第一个数的可能性。startIdx为选的数在数组中的序数。
分割:选好子串中第一个分割的部分,接着选子串中后面分割的部分。第一个树层代表分割的第一个子串的可能性。startIdx为每一个字串的“分割线”。
代码实现
class Solution(object):
def isPalin(self, s, start, end):
i, j = start, end
while i<j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def backtracking(self, s, startIdx, path, result):
if startIdx == len(s):
result.append(path[:])
return
for i in range(startIdx, len(s)):
if self.isPalin(s, startIdx, i):
path.append(s[startIdx: i+1])
self.backtracking(s, i+1, path, result)
# 每一个递归之后,startIdx都会加一(体现在i+1),直到等于字串的长度,代表当前已 经分割完s了。
path.pop()
return result
def partition(self, s):
result = []
self.backtracking(s, 0, [],result)
return result
文章来源:https://blog.csdn.net/Huiwen18/article/details/135039997
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!