当前位置：首页 > article >正文

回溯——4.分割回文串

article 2025/2/25 3:11:43

力扣题目链接

解题思路

这段代码使用回溯法解决问题，回溯法的核心思想是通过尝试各种可能性来构建解的所有组合。当发现当前路径不满足条件时，撤销上一步的操作（即回溯），并尝试其他路径。

路径：即当前已经选择的子串列表 path。
选择列表：从当前起始位置 start_index 到字符串结尾的所有子串。
结束条件：当 start_index 达到字符串 s 的长度时，说明已经分割完毕。

这种方法保证了所有可能的回文分割都能被找到，且不会遗漏。通过递归调用，程序可以在不同层次上深入地探索每一种可能的分割方式，一旦路径不符合条件或者到达最终状态，程序会通过回溯来尝试其他可能性。

完整代码如下：

class Solution:

    def partition(self, s: str) -> List[List[str]]:
        result = []
        self.backtracking(s, 0, [], result)
        return result

    def backtracking(self, s, start_index, path, result ):
        # Base Case
        if start_index == len(s):
            result.append(path[:])
            return
        
        # 单层递归逻辑
        for i in range(start_index, len(s)):
            # 若反序和正序相同，意味着这是回文串
            if s[start_index: i + 1] == s[start_index: i + 1][::-1]:
                path.append(s[start_index:i+1])
                self.backtracking(s, i+1, path, result)   # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串
                path.pop()             # 回溯

def partition(self, s: str) -> List[List[str]]:
    result = []
    self.backtracking(s, 0, [], result)
    return result

partition 是主函数，接收一个字符串 s，返回所有可能的回文串分割组合，即返回 List[List[str]] 类型的结果。
result 用来存储最终的所有结果。
通过调用 self.backtracking(s, 0, [], result) 进入回溯函数，其中：
- s 是原始字符串。
- start_index 为起始索引，这里从0开始。
- path 是当前路径（当前已经找到的回文子串组成的列表）。
- result 存放所有满足条件的路径组合。

def backtracking(self, s, start_index, path, result):
    # Base Case
    if start_index == len(s):
        result.append(path[:])
        return

Base Case：当 start_index 达到字符串末尾时，表示已经遍历完所有字符，此时将当前路径 path 加入到结果 result 中。
path[:] 是 path 的拷贝，因为 path 是列表，如果直接添加会引用同一个对象，可能导致后续操作影响已经加入的结果。

    # 单层递归逻辑
    for i in range(start_index, len(s)):
        # 若反序和正序相同，意味着这是回文串
        if s[start_index: i + 1] == s[start_index: i + 1][::-1]:
            path.append(s[start_index:i+1])
            self.backtracking(s, i+1, path, result)   # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串
            path.pop()             # 回溯

使用 for 循环来枚举从 start_index 到 len(s) 的所有可能的切割点 i。
s[start_index: i + 1] 表示从 start_index 到 i 的子串。如果这个子串是回文串（即正序等于反序），则继续进行以下步骤：
1. 选择：将这个子串加入当前路径 path。
2. 递归：调用 backtracking 进行纵向遍历，start_index 更新为 i + 1，继续切割剩余的字符串。
3. 回溯：移除 path 中最后一个元素（刚刚加入的子串），以便尝试其他可能的分割方式。