131. 分割回文串

2024-01-09 08:03:02

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

回文串?是正着读和反着读都一样的字符串。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

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

bool isCheck(string str)

? ? {

? ? ? ? int left=0;

? ? ? ? int right=str.size()-1;

? ? ? ? while(left<right)

? ? ? ? {

? ? ? ? ? ? if(str[left] != ?str[right])

? ? ? ? ? ? {

? ? ? ? ? ? ? ? return false;

? ? ? ? ? ? }

? ? ? ? ? ? left++;

? ? ? ? ? ? right--;

? ? ? ? }

? ? ? ? return true;

? ? }

? ? vector<vector<string>>ret;

? ? void find(string &s,vector<string>&vec,int cur)

? ? {

? ? ? ? string str1="";

? ? ? ? for(int i=0;i<vec.size();i++)

? ? ? ? {

? ? ? ? ? ? str1+=vec[i];

? ? ? ? }

? ? ? ? if(str1==s)

? ? ? ? {

? ? ? ? ? ? ret.push_back(vec);

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? for(int i=cur;i<s.size();i++)

? ? ? ? {

? ? ? ? ? ? string str="";

? ? ? ? ? ? str= s.substr(cur,i-cur+1);

? ? ? ? ? ? if(isCheck(str))

? ? ? ? ? ? {

? ? ? ? ? ? ? ? vec.push_back(str);

? ? ? ? ? ? ? ? find(s,vec,i+1);

? ? ? ? ? ? ? ? vec.pop_back();

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? vector<vector<string>> partition(string s) {

? ? ? ? vector<string>vec;

? ? ? ? find(s,vec, 0);

? ? ? ? return ret;

? ? }

文章来源:https://blog.csdn.net/yinhua405/article/details/135470513
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。