#P4074. 分割回文串
-
ID: 2315
Tried: 39
Accepted: 23
Difficulty: 4
分割回文串
题目内容
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是回文串 。返回 s 所有可能的分割方案。
输入描述
一个仅由小写英文字母组成的字符串。
输出描述
输出若干行，每行代表一种分割方案，用空格隔开。
样例1
输入
aab
输出
a a b
aa b
样例2
输入
a
输出
a
提示：
- 1<=s.length<=16
- s 仅由小写英文字母组成
分割回文串
题解思路
问题分析
题目要求将给定字符串 s 分割成多个子串，使得每个子串都是回文串。我们需要返回所有可能的分割方案，每一行表示一种分割方案，分割的每个子串之间用空格隔开。
解题思路
这个问题属于典型的回溯问题。回溯法可以帮助我们遍历所有可能的分割方式。关键在于如何判断每个子串是否为回文串。判断回文串的方法很简单：如果一个字符串从前往后和从后往前是一样的，那么它就是回文串。
我们可以采用以下步骤来求解这个问题：
- 回溯法遍历所有分割方式：从字符串的每一个位置进行切割，递归处理每个切割后的部分。
- 判断回文串：每次递归时，对于当前的切割部分，需要判断其是否为回文串。如果是回文串，则继续递归；如果不是，则回溯。
- 记录合法分割：当递归到字符串的末尾时，如果当前的分割方案是合法的（即所有子串都是回文串），就将其记录下来。
算法步骤
- 初始化一个空的结果列表
result来保存所有的分割方案。 - 回溯函数：从当前字符串的位置开始，尝试所有可能的切割点，对于每个切割点判断是否为回文串。
- 回溯终止条件：如果字符串被成功分割完，则将当前的分割方案加入到结果中。
- 输出所有分割方案。
复杂度分析
- 时间复杂度：由于回溯的过程中每一次递归可能会进行多次分割，而每一次的分割检查是否为回文串的时间复杂度是
O(k)（k是当前子串的长度），因此总体的时间复杂度是指数级的，最坏情况下为O(2^n)，其中n是字符串的长度。 - 空间复杂度：空间主要由递归栈和存储结果的空间组成，因此空间复杂度为
O(n)。
代码实现
Python 代码实现
def partition(s: str):
result = []
# 判断是否是回文串
def is_palindrome(sub):
return sub == sub[::-1]
# 回溯函数
def backtrack(start, path):
if start == len(s):
result.append(path[:]) # 记录当前合法的分割方案
return
for end in range(start + 1, len(s) + 1):
substr = s[start:end]
if is_palindrome(substr):
path.append(substr) # 选择当前回文子串
backtrack(end, path) # 继续递归处理剩余部分
path.pop() # 回溯
backtrack(0, [])
return result
s = input().strip()
result = partition(s)
for res in result:
print(" ".join(res))
Java 代码实现
import java.util.*;
public class Main {
// 判断是否是回文串
public static boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 回溯函数
public static 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 + 1; end <= s.length(); end++) {
String substr = s.substring(start, end);
if (isPalindrome(substr)) {
path.add(substr); // 选择当前回文子串
backtrack(s, end, path, result); // 继续递归处理剩余部分
path.remove(path.size() - 1); // 回溯
}
}
}
public static List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
List<List<String>> result = partition(s);
for (List<String> res : result) {
System.out.println(String.join(" ", res));
}
}
}
C++ 代码实现
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 判断是否是回文串
bool isPalindrome(const string& s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
}
// 回溯函数
void backtrack(const string& s, int start, vector<string>& path, vector<vector<string>>& result) {
if (start == s.length()) {
result.push_back(path); // 记录当前合法的分割方案
return;
}
for (int end = start + 1; end <= s.length(); end++) {
string substr = s.substr(start, end - start);
if (isPalindrome(substr)) {
path.push_back(substr); // 选择当前回文子串
backtrack(s, end, path, result); // 继续递归处理剩余部分
path.pop_back(); // 回溯
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
backtrack(s, 0, path, result);
return result;
}
int main() {
string s;
cin >> s;
vector<vector<string>> result = partition(s);
for (const auto& res : result) {
for (const auto& str : res) {
cout << str << " ";
}
cout << endl;
}
return 0;
}