LeetCode 131. 分割回文串

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串是正着读和反着读都一样的字符串。

例：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

方法：回溯、递归、双指针

backtrack 函数：回溯

• result 表示所有符合条件的分割方式，path 表示单个符合条件的分割方式，startIndex 表示分割的初始位置
• 若分割的初始位置等于字符串的长度，表示整个字符串已被遍历完成，即已完成对整个字符串的分割，将该种分割方式 path 加入 result，并通过返回 None 终止该次函数调用
• 若分割的初始位置并不等于字符串的长度时，表示整个字符串并未被完全遍历，即未完成对整个字符串的分割。若部分字符串 s[startIndex: i + 1] 为回文串，那么将其加入 path，继续调用 backtrack 函数

isPalindrome 函数：判断字符串是否是回文串

• 根据回文串的定义，使用双指针法，i 指向首部，j 指向尾部
• 当 i 小于 j 时，即 i 在 j 的左边，判断两个位置的字符是否相同，若相同，表示此时符合回文串定义，i 向右移动一步，j 向左移动一步，继续循环；若不同，表示此时已不符合回文串定义，返回 False，终止循环
• 若在循环的过程中并未产生返回值，表示字符串为回文串，返回 True

class Solution(object):
    def partition(self, s):
        path, result = [], []

        def backtrack(s, startIndex):
            if startIndex == len(s):
                result.append(path[:])
                return None
            
            for i in range(startIndex, len(s)):
                if isPalindrome(s[startIndex: i + 1]):
                    path.append(s[startIndex: i + 1])
                    backtrack(s, i + 1)
                    path.pop()
    
        def isPalindrome(s):
            i, j = 0, len(s) - 1
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        backtrack(s, 0)
        return result

相关知识

• 字符串的切片： str[start, end, step]
  start： 起始位置，包括
  end： 终止位置，不包括
  step： 步长

参考

代码相关：https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html