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