【LeetCode】131.分割回文串

题目描述

这道题目来自 LeetCode 131. 分割回文串。

题目描述如下：

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

输入输出示例及数据范围

思路

这道题的类型被归为回溯，实际上这道题目并不是一步回溯就能够解决的，在回溯之前，我们需要先对整个字符串进行预处理。

这道题目的要求是让我们对原字符串进行分割，分割的结果是若干个子串，且每个子串都是回文串。

那么我们解决这道题目的思路就是，对于子串s[i...j]，加入它是回文串，就把它加入到答案当中，假定字符串的长度为n，我们现在要进一步解决的问题是寻找s[j+1...n]的子串，进行分割，并将结果加入到答案当中。

当然，我们可以简单地使用双指针不断地枚举子串的范围，并判断范围内的子串是否是回文串，但是显然这种解法的时间复杂度过高。

一个更快的思路是，首先我们使用 dp 对回文串进行预处理，新开一个二维数组f，如果f[i][j] == true，则表明子串s[i...j]是回文串，此时可以将子串s[i...j]加入到答案当中，下一次回溯从j+1开始。

C++ 实现

class Solution {
public:
    vector<vector<string>> ans;
    vector<vector<bool>> f;
    vector<string> curr;
    int n;
    void solve(string &s, int i) {
        if(i == s.size()) {
            ans.push_back(curr);
            return;
        }
        for(int j=i; j<n; j++) {
            if(f[i][j]) {
                curr.push_back(s.substr(i, j - i + 1));
                solve(s, j + 1);
                curr.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<bool>(n, true));

        for(int i=n-1; i>=0; i--) {
            for(int j=i+1; j<n; j++) {	// 对回文串进行预处理
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
            }
        }

        solve(s, 0);
        return ans;
    }
};