比较简单,直接使用dfs即可。
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<string> path;
vector<vector<string>> result;
helper(s,0,path,result);
return result;
}
// [begin, end]
void helper(const string& str, int begin, vector<string>& path, vector<vector<string>>& result)
{
if (begin == str.size())
{
result.emplace_back(path);
return;
}
for (int end=begin;end<str.size();++end)
{
if (isPalindrome(str,begin,end))
{
path.emplace_back(str.substr(begin,end-begin+1));
helper(str,end+1,path,result);
path.pop_back();
}
}
}
// [begin, end]
bool isPalindrome(const string& str, int begin, int end)
{
if (begin > end)
{
return false;
}
while (begin < end)
{
if (str[begin++] != str[end--])
{
return false;
}
}
return true;
}
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); i++)
{
// 以 s[i] 为中心的最长回文子串
string s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
string s2 = palindrome(s, i, i + 1);
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
string palindrome(string& s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.size() && s[l] == s[r])
{
// 向两边展开
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中心的回文子串
return s.substr(l + 1, r - l - 1);
}
//马拉车算法
string longestPalindrome2(string s) {
string T = preProcess(s);
int n = T.length();
int *P = new int[n];
int C = 0, R = 0;
int maxLen = 0, maxC = 0;
for (int i = 1; i < n - 1; i++)
{
int i_mirror = 2 * C - i;
if (R > i)
{
P[i] = std::min(R - i, P[i_mirror]);// 防止超出 R
}
else
{
P[i] = 0;// 等于 R 的情况
}
// 碰到之前讲的三种情况时候,需要利用中心扩展法
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
{
P[i]++;
}
// 判断是否需要更新 R
if (i + P[i] > R)
{
C = i;
R = i + P[i];
}
if (P[i] > maxLen)
{
maxLen = P[i];
maxC = i;
}
}
int start = (maxC - maxLen) / 2; //最开始讲的求原字符串下标
return s.substr(start, maxLen);
}
//原字符串:abcba ===> ^#a#b#c#b#a#$
string preProcess(string s) {
int n = s.length();
if (n == 0)
{
return "^$";
}
string ret = "^";
for (int i = 0; i < n; i++)
{
ret.push_back('#');
ret.push_back(s[i]);
}
ret.append("#$");
return ret;
}
};