一:題目

二:思路

1.分析題意:這里是給定我們一個字符串 我們輸出的結果是 切割不同的位置 來得到不同的字符串
然后這些字符串是要是回文字符串 所以我們需要一個函數去判斷我們輸入的字符串是否是回文
字符串（這里用雙指針法來判斷是否為回文字符串）
2.遞歸回溯來解決
vector<vector >ans;
vector path;
1>:確定遞歸函數的參數
void backstacking(string &str,int index)
2>:確定回溯終止條件
//當我們的切割線是在字符串的末尾的時候,這時候就已經得到一種結果
if(index >= str.size()){
ans.push_back(path);
return ;
}
3>:單層邏輯
for(int i = index; i < s.size(); i++) {
//首先判斷是否是回文串
if(IsPalindromeString(s,index,i)){
string str = s.substr(index,i-index+1);//第一個參數是起始位置
//第二個參數是截取的幾個字符
path.push_back(str);
}else {
continue;
}

backstacking(str,i+1);
path.pop_back();
}
//判斷回文字符串
bool IsPalindromeString(string &s,int start,int end) {
for(int i = start,j = end; i < j; i++,j–) {
if(s[i] != s[j]) {
return false;
}
}
return true;
}

三:上碼

class Solution { public:/**思路:1.分析題意:這里是給定我們一個字符串 我們輸出的結果是 切割不同的位置 來得到不同的字符串然后這些字符串是要是回文字符串 所以我們需要一個函數去判斷我們輸入的字符串是否是回文字符串（這里用雙指針法來判斷是否為回文字符串）2.遞歸回溯來解決vector<vector<int> >ans;vector<string> path;1>:確定遞歸函數的參數void backstacking(string &str,int index)2>:確定回溯終止條件 //當我們的切割線是在字符串的末尾的時候,這時候就已經得到一種結果if(index >= str.size()){ans.push_back(path);return ;}3>:單層邏輯for(int i = index; i < s.size(); i++) {//首先判斷是否是回文串if(IsPalindromeString(s,index,i)){string str = s.substr(index,i-index+1);//第一個參數是起始位置 //第二個參數是截取的幾個字符path.push_back(str);}else {continue;}backstacking(str,i+1);path.pop_back();}//判斷回文字符串bool IsPalindromeString(string &s,int start,int end) {for(int i = start,j = end; i < j; i++,j--) {if(s[i] != s[j]) {return false;}}return true;}*/vector<vector<string> >ans;vector<string> path;void backstacking(string &s,int index) {if(index >= s.size()){ans.push_back(path);return ;}for(int i = index; i < s.size(); i++) {//首先判斷是否是回文串if(IsPalindromeString(s,index,i)){string str = s.substr(index,i-index+1);//第一個參數是起始位置 //第二個參數是截取的幾個字符path.push_back(str);}else {continue;}backstacking(s,i+1);path.pop_back();}}bool IsPalindromeString(string &s,int start,int end) {for(int i = start,j = end; i < j; i++,j--) {if(s[i] != s[j]) {return false;}}return true;}vector<vector<string>> partition(string s) {// string str = "abcdef";// string ss = str.substr(1,4);// cout << ss;// return {};backstacking(s,0);return ans;} };

總結

以上是生活随笔為你收集整理的leetcode131. 分割回文串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。