回文串是一个正着读和反着读顺序一样的字符串。"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_; };