2025年11月24日

2025年11月24日

分割回文串

class Solution {
private:vector<string>ans;//记录一组分割结果vector<vector<string>>ret;//记录返回结果，本题答案vector<vector<bool>>dp;//dp[i][j]记录子串s[i][j]是否是回文子串int n;
public:void dfs(string s,int i){if(i==n){ret.push_back(ans);return;}for(int j=i;j<n;j++){if(dp[i][j]==true){ans.push_back(s.substr(i, j - i + 1));dfs(s,j+1);ans.pop_back();}}}vector<vector<string>> partition(string s) {n=s.size();dp.assign(n,vector<bool>(n,true));//初始化dp全为true//判定子串是否为回文串for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++){dp[i][j]=dp[i+1][j-1]&&(s[i]==s[j]);//因为要由串s[i+1][j-1]定s[i][j],所以i+1的位置要先确定，所以i倒着循环}}dfs(s,0);//分割点从0开始搜return ret;}
};

取子串s.substr(i, j - i + 1)