Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

问题描述

给定一个字符串 s，将 s 分割成一些字符串，使得这些字符串都是回文。返回所有满足条件的分割。

样例

输入: 'aab'
输出: 
[
    ['aa', 'b'],
    ['a', 'a', 'b']
]

解法 1

这道题要求将指定的字符串 s 分割成一些字符串，使得这些字符串都是回文。一个简单的思路是用递归解决这个问题，假设 s 的前 i 个字符组成的字符串是回文，则后 n-i 个字符可以递归调用原函数得到其满足条件的分割，s 的前 i 个字符组成的字符串加上这些分割即可得到字符串 s 的分割。

参考代码:

class Solution:  
    def partition(self, s):
        if not s:
            return [[]]
        elif len(s) == 1:
            return [[s]]
        n = len(s)
        res = []
        for i in range(1, n+1):
            j, k = 0, i - 1
            while j < k and s[j] == s[k]:
                j += 1
                k -= 1
            if j >= k:
                tmp = self.partition(s[i:])
                if not tmp:
                    res.append([s[:i]])
                else:
                    for _ in tmp:
                        res.append([s[:i]] + _)
        return res

解法 2

也可以采用回溯算法来解决这个问题。将字符串从左到右扫描，每次有回文时就添加到当前的字符串数组 cur 中。设函数 helper(i) 表示将字符串从第 i+1 个位置开始向右扫描，则

• 若 i==n，则说明向右扫描完成，将当前的字符串数组 cur 添加到结果中
• 对剩下的位置进行循环，若当前位置到循环位置组成的字符串是回文，则添加到当前的字符串数组 cur 中，并从新的位置进行扫描。在扫描完成时，应当将刚刚添加进数组 cur 的字符串弹出

参考代码:

class Solution:  
    def partition(self, s):
        if not s:
            return [[]]
        
        n = len(s)
        res = []
        cur = []
        def helper(i):
            if i == n:
                res.append(cur[:])
            for j in range(i+1, n+1):
                l, r = i, j - 1
                while l < r and s[l] == s[r]:
                    l += 1
                    r -= 1
                if l >= r:
                    cur.append(s[i: j])
                    helper(j)
                    cur.pop()
            
        helper(0)
        return res

解法 3