原题链接🔗：分割回文串
难度：中等⭐️⭐️
题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
提示：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
回文串
回文串，也称为回文字符串，是指一个字符串正读和反读都一样。例如，“level”和“madam”都是英语中的回文串。在编程中，经常会遇到判断一个字符串是否是回文串的问题。这个问题可以通过以下步骤解决：
- 标准化：通常首先将字符串转换为统一的大小写（通常是小写），以忽略大小写的差异。
- 去除空白和标点：如果问题要求忽略空格、标点和特殊字符，需要先将这些从字符串中去除。
- 比较字符：从字符串的两端开始，逐个比较对应位置的字符是否相同。
- 判断结果：如果在比较过程中发现有不匹配的字符，那么该字符串就不是回文串。如果所有对应位置的字符都匹配，那么该字符串是回文串。
以下是一个简单的Python函数，用来判断一个字符串是否是回文串：
def is_palindrome(s):# 将字符串转换为小写并去除非字母数字字符cleaned = ''.join(c for c in s.lower() if c.isalnum())# 比较字符串和它的反转是否相同return cleaned == cleaned[::-1]# 示例
print(is_palindrome("A man, a plan, a canal: Panama")) # 应该返回True
在这个函数中，使用了字符串的切片功能cleaned[::-1]来获取它的反转，这是一种简洁的方法来检查字符串是否是回文。
题解
- 解题思路：
这个问题可以使用动态规划（Dynamic Programming, DP）来解决。以下是解题的步骤：
定义状态：设dp[i]表示字符串s[0…i-1]的分割方案数。
状态转移方程：对于每个i，检查s[j]到s[i-1]（j从0到i-1）是否是回文串。如果是，那么dp[i]可以从dp[j]转移过来。
初始化：dp[0] = 1，表示空字符串有一种分割方案。
计算顺序：按照从左到右的顺序计算dp[i]。
回文串检查：可以使用双指针（快慢指针）的方法来检查s[j]到s[i-1]是否是回文串。
状态更新：对于每个i，更新dp[i]为所有可以形成回文串的j的dp[j]之和。
结果：最终dp[s.length()]即为所求的不同分割方案数。
- c++ demo：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;// 判断字符串是否是回文
bool isPalindrome(const string& s) {return equal(s.begin(), s.end(), s.rbegin());
}// 辅助函数，用于回溯找到所有分割方案
void findPartitions(const string& s, int start, vector<string>& current, vector<vector<string>>& result) {if (start == s.size()) {if (!current.empty()) {result.push_back(current);}return;}for (int end = start; end < s.size(); ++end) {if (isPalindrome(s.substr(start, end - start + 1))) {current.push_back(s.substr(start, end - start + 1));findPartitions(s, end + 1, current, result);current.pop_back();}}
}// 返回所有可能的分割方案
vector<vector<string>> partitionPalindromes(const string& s) {vector<vector<string>> result;vector<string> current;findPartitions(s, 0, current, result);return result;
}int main() {string s = "abcba";vector<vector<string>> partitions = partitionPalindromes(s);for (const auto& part : partitions) {for (const string& str : part) {cout << str << " ";}cout << "\n";}cout << "Total partitions: " << partitions.size() << endl;return 0;
}
- 运行结果：
a b c b a
a bcb a
abcba
Total partitions: 3
- 代码仓库地址：partitionPalindromes