题目描述

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

示例 1：

输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

解题思路

这道题使用回溯算法来解决。核心思路是：

  1. 对于每个位置，有两种选择：将当前字符加入到前一个子串中，或者开始一个新的子串
  2. 当遍历完整个字符串时，检查所有子串是否都是回文串
  3. 如果是，则将当前分割方案加入结果集

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// isPalindrome 检查字节切片是否为回文
func isPalindrome(bytes []byte) bool {
	for left, right := 0, len(bytes)-1; left < right; left, right = left+1, right-1 {
		if bytes[left] != bytes[right] {
			return false
		}
	}
	return true
}

// partition 分割字符串为回文子串的所有可能方案
func partition(s string) [][]string {
	if len(s) == 0 {
		return [][]string{}
	}

	// currentPartition 存储当前的分割方案（以字节形式）
	currentPartition := [][]byte{[]byte{s[0]}}
	ans := [][]string{}

	// backtrack 回溯函数，从指定索引开始继续分割
	var backtrack func(index int)
	backtrack = func(index int) {
		// 如果已经处理完所有字符
		if index == len(s) {
			// 检查当前分割方案中的所有子串是否都是回文
			partitionStrings := make([]string, len(currentPartition))
			for i, subBytes := range currentPartition {
				if !isPalindrome(subBytes) {
					return // 如果有非回文子串，直接返回
				}
				partitionStrings[i] = string(subBytes)
			}
			// 所有子串都是回文，加入结果集
			ans = append(ans, partitionStrings)
			return
		}

		// 选择1：将当前字符加入到最后一个子串中
		currentPartition[len(currentPartition)-1] = append(currentPartition[len(currentPartition)-1], s[index])
		backtrack(index + 1)
		// 回溯：移除刚才添加的字符
		currentPartition[len(currentPartition)-1] = currentPartition[len(currentPartition)-1][:len(currentPartition[len(currentPartition)-1])-1]

		// 选择2：开始一个新的子串
		currentPartition = append(currentPartition, []byte{s[index]})
		backtrack(index + 1)
		// 回溯：移除刚才添加的子串
		currentPartition = currentPartition[:len(currentPartition)-1]
	}

	// 从第二个字符开始回溯（第一个字符已经在初始化时处理）
	backtrack(1)
	return ans
}