分割回文串

题解思路

问题分析

题目要求将给定字符串 s 分割成多个子串，使得每个子串都是回文串。我们需要返回所有可能的分割方案，每一行表示一种分割方案，分割的每个子串之间用空格隔开。

解题思路

这个问题属于典型的回溯问题。回溯法可以帮助我们遍历所有可能的分割方式。关键在于如何判断每个子串是否为回文串。判断回文串的方法很简单：如果一个字符串从前往后和从后往前是一样的，那么它就是回文串。

我们可以采用以下步骤来求解这个问题：

1. 回溯法遍历所有分割方式：从字符串的每一个位置进行切割，递归处理每个切割后的部分。
2. 判断回文串：每次递归时，对于当前的切割部分，需要判断其是否为回文串。如果是回文串，则继续递归；如果不是，则回溯。
3. 记录合法分割：当递归到字符串的末尾时，如果当前的分割方案是合法的（即所有子串都是回文串），就将其记录下来。

算法步骤

1. 初始化一个空的结果列表 result 来保存所有的分割方案。
2. 回溯函数：从当前字符串的位置开始，尝试所有可能的切割点，对于每个切割点判断是否为回文串。
3. 回溯终止条件：如果字符串被成功分割完，则将当前的分割方案加入到结果中。
4. 输出所有分割方案。

复杂度分析

• 时间复杂度：由于回溯的过程中每一次递归可能会进行多次分割，而每一次的分割检查是否为回文串的时间复杂度是 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;
}

Leetcode 61.分割回文串-原题链接

题目内容

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

输入描述

一个仅由小写英文字母组成的字符串。

输出描述

输出若干行，每行代表一种分割方案，用空格隔开。

样例1

输入

aab

输出

a a b
aa b

样例2

输入

a

输出

a

提示：

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