A49999. 切割回文
填空题
较难
知识点
题目描述
切割回文
题目描述
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入:
"aab"
输出:
[
["aa","b"],
["a","a","b"]
]
参考答案
class Solution {
public:
vector<vector<string>> result;
vector<vector<string>> partition(string s) {
vector<string> temp;
getAns(0, s, temp, s.length(), result);
return result;
}
void getAns(int start, string s, vector<string> temp, int num, vector<vector<string>>& result)
{
if(num == 0)
result.push_back(temp);
else
{
for(int i = 1; i <= num; i ++)
{
string s1 = s.substr(start, i);
if(isRev(s1))
{
temp.push_back(s1);
getAns(start + i, s, temp, num - i, result);
temp.pop_back();
}
}
}
}
int isRev(string s)
{
int i = 0;
int j = s.length() - 1;
while(i < j)
{
if(s[i] == s[j])
{
i ++;
j --;
}
else
break;
}
if(i >= j)
return 1;
else
return 0;
}
};答案解析
这道题的回溯过程为，给定一个开始位置，从这个位置开始分别遍历长度为i的子串，如果该串为回文串，则向下遍历，否则返回。但是时间复杂度不是很好。
上一题
下一题