leetcode：647. 回文子串

题目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

  1. 输入：s = "abc"
  2. 输出：3
  3. 解释：三个回文子串: "a", "b", "c"

示例 2：

  1. 输入：s = "aaa"
  2. 输出：6
  3. 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解答 & 代码

解法一：中心扩展法（双指针）

外循环遍历每种可能的回文中心，然后内循环以这个回文中心为起点向两边扩展

需要注意的是，回文中心可能是一个数（回文子串长度为奇数）也可能是相邻的两个数（回文子串长度为偶数）。因此可以用两个变量 mid1、mid2 来代表回文子串中心的下标。如果 mid1==mid2，则回文中心是一个数，否则是相邻的两个数。
eg. 长为 3 的字符串，回文子串中心的下标取值 (mid1, mid2) 依次为 (0, 0)->(0,1),->(1,1)->(1,2)->(2,2)

  1. class Solution {
  2. public:
  3.     int countSubstrings(string s) {
  4.         int len = s.size();
  5.         int result = 0;        // 回文子串数目
  6.         int mid1 = 0;        // 回文子串中心 1 下标
  7.         int mid2 = 0;        // 回文子串中心 2 下标
  8.         // 遍历每对回文子串中心的取值
  9.         while(mid1 < len && mid2 < len)
  10.         {
  11.             int left = mid1;    // 回文子串的左边界
  12.             int right = mid2;    // 回文子串的右边界
  13.             // 从回文子串中心向两边扩展
  14.             while(left >= 0 && right < len && s[left] == s[right])
  15.             {
  16.                 ++result;        // 回文子串数目 +1
  17.                 --left;
  18.                 ++right;
  19.             }
  21.             // 回文子串中心右移
  22.             if(mid1 < mid2)
  23.                 ++mid1;
  24.             else
  25.                 ++mid2;
  26.         }
  27.         return result;
  28.     }
  29. };

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 [中等] 647. 回文子串 - 图1：外循环遍历回文子串中心，需要迭代 2N-1 次。内循环从中心向两边扩展，时间复杂度 O(N)
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：6.2 MB, 在所有 C++ 提交中击败了73.93% 的用户

解法二：Manacher 算法（马拉车算法）

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 O(N)
  • 空间复杂度 O(N)