647. 回文子串【双指针：两种对称情况-回文串】（字符串S中回文子串的个数）

647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：
1 <= s.length <= 1000
s 由小写英文字母组成

---

思路：

（1）跟 字符串s 的长度 是偶数还是奇数 无关；
（2）回文子串注意点：有两种情况的 对称。

---

Java代码1：中心扩散法

中心扩散法，向两边扩散：--left、++right

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        int ans = 0;
        for (int i = 0; i < 2 * len - 1; ++i) {
            int left = i / 2;
            int right = i / 2 + i % 2;
            // i=0, l=0; r=0;  i=4, l=2; r=2;  i=2(n-1), l=n-1; r=n-l;
            // i=1, l=0; r=1;  i=5, l=2; r=3; 
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                --left;
                ++right;
                ++ans;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度O(n^2)、空间复杂度O(1)

---

Java代码2：中心扩散法

中心扩散法，向两边扩散：--left、++right

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        int ans = 0;
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j <= 1; ++j) {
                int left = i;
                int right = i + j;
                while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                    --left;
                    ++right;   //中心扩散法，向两边扩散：--left、++right
                    ++ans;
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

执行用时：3 ms, 在所有 Java 提交中击败了85.20%的用户
内存消耗：39.3 MB, 在所有 Java 提交中击败了82.84%的用户