分割回文串
题目要求
给定一个字符串 s，要求编写一个算法，将字符串 s 分割成若干子串，使得每个子串都是回文串。算法需要返回字符串 s 所有可能的分割方案。
解题思路
解决这个问题可以采用回溯算法的思想。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个有效的解，或者不可能产生一个有效的解，那么回溯算法会丢弃该候选解。这个过程重复进行，直到找到所有可能的解。
对于这个问题，我们可以按照以下步骤来设计我们的回溯算法：
- 从字符串的开头开始，尝试所有可能的分割方式。
- 对于每一种分割方式，检查分割出来的前缀字符串是否是回文串。
- 如果前缀字符串是回文串，则将其加入到当前分割方案中，并对剩余的字符串继续进行分割。
- 如果前缀字符串不是回文串，则跳过这种分割方式，尝试下一种分割方式。
- 当到达字符串的末尾时，如果整个字符串都被分割成了回文串，则将当前分割方案加入到结果列表中。
- 在整个过程中，我们需要用一个变量来保存当前的分割方案，以便在达到字符串末尾时可以将其加入到结果列表中。
- 回溯的过程中，每次从结果中移除最后一个加入的回文串，以尝试新的分割方案。
通过这样的回溯过程，我们可以找到所有可能的将字符串分割成回文串的方案。
Golang 版本
package main
import "fmt"
func partition(s string) [][]string {
var result [][]string
var path []string
backtrack(s, path, &result)
return result
}
func backtrack(s string, path []string, result *[][]string) {
if len(s) == 0 {
temp := make([]string, len(path))
copy(temp, path)
*result = append(*result, temp)
return
}
for i := 1; i <= len(s); i++ {
if isPalindrome(s[:i]) {
path = append(path, s[:i])
backtrack(s[i:], path, result)
path = path[:len(path)-1]
}
}
}
func isPalindrome(s string) bool {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
func main() {
s := "aab"
result := partition(s)
fmt.Println(result)
}
这段代码定义了一个partition函数，它接受一个字符串s并返回一个二维字符串切片，其中包含了所有可能的将s分割成回文串的方案。backtrack是一个递归函数，用于执行回溯算法。isPalindrome函数用于检查一个字符串是否是回文串。在main函数中，我们调用partition函数并打印出结果。
C++版本
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
backtrack(s, 0, path, result);
return result;
}
private:
void backtrack(const string &s, int start, vector<string> &path, vector<vector<string>> &result) {
if (start == s.size()) {
result.push_back(path);
return;
}
for (int end = start; end < s.size(); ++end) {
if (isPalindrome(s, start, end)) {
path.push_back(s.substr(start, end - start + 1));
backtrack(s, end + 1, path, result);
path.pop_back();
}
}
}
bool isPalindrome(const string &s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) {
return false;
}
}
return true;
}
};
int main() {
Solution solution;
string s = "aab";
vector<vector<string>> result = solution.partition(s);
for (const auto &partition : result) {
for (const auto &palindrome : partition) {
cout << palindrome << " ";
}
cout << endl;
}
return 0;
}
这段 C++代码定义了一个Solution类，其中包含了解决问题的partition方法。partition方法接受一个字符串s并返回一个二维字符串向量，其中包含了所有可能的将s分割成回文串的方案。backtrack是一个私有方法，用于执行回溯算法。isPalindrome方法用于检查字符串的一个子串是否是回文串。在main函数中，我们创建了一个Solution对象，调用partition方法并打印出结果。
Python 版本
def partition(s):
def backtrack(start, path):
if start == len(s):
result.append(path[:])
return
for end in range(start, len(s)):
if s[start:end+1] == s[start:end+1][::-1]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
result = []
backtrack(0, [])
return result
# 测试代码
s = "aab"
print(partition(s))
这段 Python 代码定义了一个partition函数，它接受一个字符串s并返回一个列表，其中包含了所有可能的将s分割成回文串的方案。backtrack是一个嵌套函数，用于执行回溯算法。它检查从当前start位置到任意end位置的子串是否为回文串，如果是，则将其添加到当前路径path中，并继续递归。当start等于字符串长度时，将当前路径添加到结果列表中。在测试代码中，我们调用partition函数并打印出结果。
Java 版本
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
path.add(s.substring(start, end + 1));
backtrack(s, end + 1, path, result);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int low, int high) {
while (low < high) {
if (s.charAt(low++) != s.charAt(high--)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "aab";
List<List<String>> result = solution.partition(s);
for (List<String> partition : result) {
System.out.println(partition);
}
}
}
这段 Java 代码定义了一个Solution类，其中包含了解决问题的partition方法。partition方法接受一个字符串s并返回一个列表，其中包含了所有可能的将s分割成回文串的方案。backtrack是一个私有辅助方法，用于执行回溯算法。isPalindrome方法用于检查字符串的一个子串是否是回文串。在main方法中，我们创建了一个Solution对象，调用partition方法并打印出结果。
Rust 版本
fn partition(s: String) -> Vec<Vec<String>> { fn is_palindrome(s: &str) -> bool { s.chars().eq(s.chars().rev()) } fn backtrack(s: &str, start: usize, path: &mut Vec<String>, result: &mut Vec<Vec<String>>) { if start == s.len() { result.push(path.clone()); return; } for end in start + 1..=s.len() { if is_palindrome(&s[start..end]) { path.push(s[start..end].to_string()); backtrack(s, end, path, result); path.pop(); } } } let mut result = Vec::new(); backtrack(&s, 0, &mut Vec::new(), &mut result); result } fn main() { let s = "aab".to_string(); let partitions = partition(s); for p in partitions { println!("{:?}", p); } }
这段 Rust 代码定义了一个partition函数，它接受一个字符串s并返回一个向量，其中包含了所有可能的将s分割成回文串的方案。is_palindrome是一个辅助函数，用于检查一个字符串片段是否是回文。backtrack是一个递归函数，用于执行回溯算法。在main函数中，我们调用partition函数并打印出结果。
总结
上述代码提供了一个字符串分割问题的解决方案，目标是将给定的字符串s分割成若干个回文子串。无论是哪种编程语言，核心算法都是基于回溯的方法。以下是解法的关键步骤：
-
回溯函数：定义一个回溯函数
backtrack，它递归地尝试所有可能的分割方法，并将当前位置之后的子串分割成回文串。 -
终止条件：当回溯函数的起始位置达到字符串的末尾时，说明找到了一种分割方法，将当前路径添加到结果集中。
-
递归分割：从当前位置开始，逐步增加子串的长度，如果当前子串是回文，则将其添加到当前路径，并从子串的下一个位置继续递归。
-
回文判断：定义一个辅助函数
is_palindrome，用于判断当前子串是否是回文。 -
路径和结果：使用一个动态数组（或向量）来存储当前的分割路径，使用另一个动态数组（或向量）来存储所有可能的分割结果。
-
主函数：在主函数中，初始化结果集，调用回溯函数开始递归，并最终返回或打印所有可能的分割方案。
不同编程语言的实现细节有所不同，但算法的核心思想是一致的。例如，在 Rust 中使用Vec来存储路径和结果，在 Python 中使用列表，而在 C++和 Java 中则使用vector和ArrayList。此外，字符串的处理方式也根据语言特性有所不同，如在 Rust 中使用切片，在 Python 中使用切片操作，在 C++和 Java 中使用substr方法。