LeetCode 算法：分割回文串 c++

原题链接🔗：分割回文串
难度：中等⭐️⭐️

题目

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

示例 1：

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

示例 2：

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

提示：

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

回文串

回文串，也称为回文字符串，是指一个字符串正读和反读都一样。例如，“level”和“madam”都是英语中的回文串。在编程中，经常会遇到判断一个字符串是否是回文串的问题。这个问题可以通过以下步骤解决：

1. 标准化：通常首先将字符串转换为统一的大小写（通常是小写），以忽略大小写的差异。
2. 去除空白和标点：如果问题要求忽略空格、标点和特殊字符，需要先将这些从字符串中去除。
3. 比较字符：从字符串的两端开始，逐个比较对应位置的字符是否相同。
4. 判断结果：如果在比较过程中发现有不匹配的字符，那么该字符串就不是回文串。如果所有对应位置的字符都匹配，那么该字符串是回文串。

以下是一个简单的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]来获取它的反转，这是一种简洁的方法来检查字符串是否是回文。

题解

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()]即为所求的不同分割方案数。

2. 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

3. 代码仓库地址：partitionPalindromes