分割回文串
📌 定义
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例:
输入: s = "aab"
输出: [["a","a","b"],["aa","b"]]
输入: s = "a"
输出: [["a"]]
核心思路
使用回溯算法进行字符串切割：
- 选择：在当前位置切割，如果是回文串则继续
- 探索：递归处理剩余字符串
- 撤销：回溯，尝试其他切割位置
Go 代码
Go 实现
func partition(s string) [][]string {
result := [][]string{}
path := []string{}
var backtrack func(start int)
backtrack = func(start int) {
if start == len(s) {
temp := make([]string, len(path))
copy(temp, path)
result = append(result, temp)
return
}
for end := start; end < len(s); end++ {
if isPalindrome(s, start, end) {
path = append(path, s[start:end+1])
backtrack(end + 1)
path = path[:len(path)-1]
}
}
}
backtrack(0)
return result
}
func isPalindrome(s string, left, right int) bool {
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}思路展开
s = "aab"
backtrack(0, []):
切割[0:1]="a" (回文) ✓
backtrack(1, ["a"]):
切割[1:2]="a" (回文) ✓
backtrack(2, ["a","a"]):
切割[2:3]="b" (回文) ✓
backtrack(3, ["a","a","b"]) → 收集
切割[1:3]="ab" (非回文) ✗
切割[0:2]="aa" (回文) ✓
backtrack(2, ["aa"]):
切割[2:3]="b" (回文) ✓
backtrack(3, ["aa","b"]) → 收集
切割[0:3]="aab" (非回文) ✗
结果: [["a","a","b"], ["aa","b"]]
经典题目
- 分割回文串 - LeetCode 131
- 分割回文串 II - LeetCode 132（最少切割次数）