链接
https://leetcode-cn.com/problems/palindrome-partitioning/
耗时
解题:24 min
题解:35 min
题意
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
思路
以位置 0 为子串首字符,每找到一个回文串,把这个回文串加入划分数组,再以这个子串的下一个位置到原字符串的结尾作为新的字符串(重复子问题)进行上述过程,当子串的下一个位置是原字符串的结尾,将划分数组加入结果。回溯回来的时候,从划分数组中删除当前的回文串。
时间复杂度:
O
(
n
2
2
n
)
O(n^22^n)
O(n22n)
AC代码
class Solution {
public:
string s;
vector<string> res;
vector<vector<string>> ans;
int len;
bool IsPalindromeString(string s) {
int n = s.size();
for(int i = 0; i < n/2; ++i) {
if(s[i] != s[n-1-i])
return false;
}
return true;
}
void dfs(int start_pos) {
if(start_pos == len) {
ans.push_back(res);
return ;
}
for(int i = start_pos; i < len; ++i) {
string tes_str = s.substr(start_pos, i-start_pos+1);
if(IsPalindromeString(tes_str)) {
res.push_back(tes_str);
dfs(i+1);
res.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
this->s = s;
len = s.size();
dfs(0);
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)