回文串是一个正着读和反着读顺序一样的字符串。"aba" 是回文串，"abba" 是回文串，"abc" 不是回文串。
回文串的题目，都要使用一个基本的逻辑，就是判断当前这个字符串是不是回文串。以 c++ 为例，代码如下。这种方法也可以称为双指针法，两个指针从字符串的两端向中间遍历每个字符，如果中间发现两个字符不相同，则不是回文字符串；遍历到最后，说明是回文串。
bool isPalindrome(const string s) {
int len = s.size();
if (len <= 1) {
return true;
}
int left = 0;
int right = len - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
}双指针法，在其它数据结构题目中也会用到，比如链表中会用到快慢指针，也属于双指针。快速排序算法中，给选中的数据找到合适的位置，也会使用两个指针从两边向中间对数据进行遍历，也属于双指针。
判断回文串，也可以使用从中间向两边的方法，使用这种方法时，首先需要判断字符串的长度是奇数还是偶数，如果是奇数的话，那么两个指针从中间的位置开始向两边遍历；偶数的话，两个指针分别从中间两个元素的位置开始遍历。
没有特殊要求的话，优先选用从两边向中间的方式来判断一个字符串是不是回文串。
1 验证回文串
leetcode：验证回文串
题目要求判断给定的字符串是不是回文串，如果是回文串，则返回 true；如果原字符串不是回文串，那么最多可以删除一个字符，如果删除一个字符之后的字符串是回文串，那么返回 true，否则返回 false。
1.1 基础算法
（1）判断原字符串是不是回文串，是回文串返回 true；否则执行第 2 步
（2）遍历字符串的每个字符，分别将每个字符删除，判断删除字符之后的字符串是不是回文串。
如果是回文串，则返回 true，停止遍历；如果字符遍历结束，则返回 false。
这种算法的时间复杂度是 O(n 的平方)，偏大，所以优先选用第二种方法，第二种算法的时间复杂度是 O(n)。
1.2 双指针，动态判断
（1）使用双指针，从两边向中间遍历每个字符
（2）如果遍历到两个字符不相等，则讨论如下两种情况
① 删除左边的字符，判断子串是不是回文串，是的话则返回 true
② 删除右边的字符，判断子串是不是回文串，是的话返回 true
如果两种情况都不是回文串，那么返回 false。
（3）如果字符串遍历结束，都满足回文串的要求，则返回 true
class Solution {
public:
bool validPalindrome(string s) {
int len = s.size();
int left = 0;
int right = len - 1;
bool result = true;
while (left < right) {
if (s[left] != s[right]) {
if (isPalindrome(s.substr(left + 1, right - left))) {
return true;
}
if (isPalindrome(s.substr(left, right - left))) {
return true;
}
return false;
}
left++;
right--;
}
return true;
}
bool isPalindrome(const string s) {
int len = s.size();
if (len <= 1) {
return true;
}
int left = 0;
int right = len - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
}
};2 最长回文子串
leetcode：最长回文子串
一个字符串 s，找到 s 中最长的回文子串。
2.1 动态规划
将所有的子串的情况都遍历到，在遍历的过程中，判断子串是不是回文串，如果是回文串并且长度比已有的回文串长的话，那么就更新结果。属于动态规划算法。
这个算法的事件复杂度是 O(n 的平方)，时间复杂度较高，在 leetcode 上运行时会超时。
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
for (int i = 0; i < size; i++) {
for (int j = i; j < size; j++) {
if (isPalindrome(s.substr(i, j - i + 1))) {
if (j - i + 1 > max_length) {
max_length = j - i + 1;
max_str = s.substr(i, j - i + 1);
}
}
}
}
return max_str;
}
private:
bool isPalindrome(string s) {
int size = s.size();
int i = 0;
int j = size - 1;
while (i < j) {
if (s[i] != s[j]) {
return false;
}
i++;
j--;
}
return true;
}
private:
int max_length = 0;
string max_str;
};这个题目要找的是最长回文子串，我们能想到 j 的遍历从大向小遍历。这样遍历的话就是先遍历长度大的字符串，再遍历长度小的字符串。当第一个遍历到一个字符串是回文串，那么这个回文串就是长度最大的回文串，就可以直接返回。从小向大进行遍历，当遍历到这个字符串是回文串的时候，仍然不能返回，因为不能确定这个字符串是不是长度最大的回文串，需要将所有情况都遍历完毕才能确定最大的回文字符串。再进一步思考，我们可以以子串的长度作为遍历的依据，长度从大到小进行遍历。
如下是使用 c 语言实现的算法。
char ret[1001] = {'\0'};
char* longestPalindrome(char* s) {
int length = strlen(s);
if (length <= 1) {
return s;
}
memset(ret, 0, 1001);
for (int len = length; len >= 1; len--) {
for (int i = 0; i < length; i++) {
if (i + len - 1 >= length) {
break;
}
int start_index = i;
int end_index = i + len - 1;
if (isPalindrome(s, start_index, end_index)) {
int index = 0;
for (int i = start_index; i <= end_index; i++) {
ret[index] = s[i];
index++;
}
return ret;
}
}
}
return NULL;
}
int isPalindrome(char *s, int start_index, int end_index) {
while (start_index < end_index) {
if (s[start_index] != s[end_index]) {
return 0;
}
start_index++;
end_index--;
}
return 1;
}官方题解中也是遍历了子串的长度，但是是从小到大进行遍历的，同时还记录了已经遍历过的子串的结果。当判断长度较大的字符串是不是回文串时，可以直接基于历史记录来做判断。这也是动态规划常用的思路，就是在遍历的过程中记录历史信息，这样在后边的遍历中可以直接使用已经记录的历史信息。
官方题解中，正因为长度是从小到大进行遍历的，所以在遍历的时候判断字符串是不是回文串的时候，可以使用历史信息进行判断。因为 s[i][j] 比 s[i + 1][j - 1] 的长度要大，后者是不是回文串已经是确定的。
2.2 中心扩展法
leetcode 官方题解中提供了另外一种方法，中心扩展法。
这个问题的多种算法之间的区别就是遍历的对象不一样：
（1）两级遍历，遍历字符串的索引
（2）两级遍历，一级遍历子串的长度，一级遍历字符串的索引
（3）中心扩展法也是遍历字符串的索引，不过在计算逻辑上，是把索引当成了要遍历的子串的中心
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
int start = 0;
int end = 0;
for (int i = 0; i < size; i++) {
int left1 = i;
int right1 = i;
int left2 = i;
int right2 = i + 1;
// 从中心向两边扩展，要考虑两种情况
// 奇数的情况，偶数的情况
centerExpand(s, left1, right1);
centerExpand(s, left2, right2);
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return s.substr(start, end - start + 1);
}
void centerExpand(string &s, int &left, int &right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
// 循环退出，说明最后一个索引不满足回文串的情况
// 要么是 left 和 right 越界了，要么是当前这两个字符不相等
// 这两种情况下，left 需要 ++, right 需要 --
left++;
right--;
}
};3 分割回文子串
leetcode：分割回文子串
本文，用基础的算法去思考的话，很难思考下去，遇到这种情况一般要考是不是可以使用递归算法。
class Solution {
public:
vector<vector<string>> partition(string s) {
partitionHelper(s, 0);
return result_;
}
void partitionHelper(const string &s, int start_index) {
int len = s.size();
if (start_index >= len) {
result_.push_back(one_instance_);
return;
}
for (int i = start_index; i < len; i++) {
if (isPalindome(s, start_index, i)) {
one_instance_.push_back(s.substr(start_index, i - start_index + 1));
partitionHelper(s, i + 1);
one_instance_.pop_back();
}
}
}
bool isPalindome(const string &s, int start, int end) {
if (start >= end) {
return true;
}
if (flag[start][end] == 1) {
return true;
}
if (flag[start][end] == -1) {
return false;
}
int tmp_start = start;
int tmp_end = end;
while (tmp_start < tmp_end) {
if (s[tmp_start] != s[tmp_end]) {
flag[tmp_start][tmp_end] = -1;
flag[start][end] = -1;
return false;
}
tmp_start++;
tmp_end--;
}
flag[start][end] = 1;
return true;
}
private:
int flag[20][20] = {0};
vector<vector<string>> result_;
vector<string> one_instance_;
};
![[NOIP2015 提高组] 子串](https://img-blog.csdnimg.cn/direct/4542405d8c714086bdfa49e2654f86db.jpeg)
