跳转至

131. 分割回文串

题目

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

示例 1:

输入: s = "aab"

输出: [["a","a","b"],["aa","b"]]

示例 2:

输入: s = "a"

输出: [["a"]]

题解

回溯-子集问题

假设每对相邻字符之间有个逗号，那么就看每个逗号是选还是不选。也可以理解成：是否要把 s[i] 当成分割出的子串的最后一个字符。注意 s[n−1] 一定是最后一个字符，一定要选。

Go
func isPalindrome(s string, left, right int) bool {
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

func partition(s string) (ans [][]string) {
    n := len(s)
    path := []string{}

    // 考虑 i 后面的逗号怎么选
    // start 表示当前这段回文子串的开始位置
    var dfs func(int, int)
    dfs = func(i, start int) {
        if i == n { // s 分割完毕
            ans = append(ans, slices.Clone(path))
            return
        }

        // 不选 i 和 i+1 之间的逗号（i=n-1 时一定要选）
        if i < n-1 {
            // 考虑 i+1 后面的逗号怎么选
            dfs(i+1, start)
        }

        // 选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）
        if isPalindrome(s, start, i) {
            path = append(path, s[start:i+1])
            // 考虑 i+1 后面的逗号怎么选
            // start=i+1 表示下一个子串从 i+1 开始
            dfs(i+1, i+1)
            path = path[:len(path)-1] // 恢复现场
        }
    }

    dfs(0, 0)
    return
}
Python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        # 返回子串str[s, e]是否为回文串
        def is_palindrome(l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        # 以start作为某个子串的起点进行拆分，判断[start, j]是否为回文串，并进行递归
        def backtrack(start: int):
            if start == n:
                # start到达字符串终点，说明得到一种方案
                ans.append(part[:])
                return

            for j in range(start, n):       # 枚举子串终点，拆分一个子串[start, j]
                if not is_palindrome(start, j):
                    continue                # 非回文串，跳过
                part.append(s[start: j+1])  # 子串为回文串，拆分子串
                backtrack(j + 1)            # 以j+1为下一个子串的起点，递归
                part.pop()                  # 回溯，还原现场

        ans = []    # 存储所有方案
        part = []   # 构造某一种方案
        n = len(s) 

        backtrack(0)    # 以下标0为起点开始构造

        return ans

复杂度

  • 时间复杂度: \(O(n \ 2^n)\)，其中 \(n\) 为 \(s\) 的长度。每次都是选或不选，递归次数为一个满二叉树的节点个数，那么一共会递归 \(O(2^n)\) 次（等比数列和），再算上加入答案时复制 path 需要 \(O(n)\) 的时间，所以时间复杂度为 \(O(n \ 2^n)\)。
  • 空间复杂度: \(O(n)\)。

参考