LeetCode647. 回文子串

博主： Mashiro
发布时间：2023 年 01 月 18 日
625 次浏览
暂无评论
3329字数
分类：算法

# LeetCode647. 回文子串

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

**示例1**

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

**示例2**

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

## Manacher 算法

```java
/**
     * Manacher
     */
    public int countSubstrings(String s) {
        int len = s.length();
        StringBuilder sb = new StringBuilder("$#");
//        解决回文串奇数长度和偶数长度的问题，处理方式是在所有的相邻字符中间插入 '#' ，这样可以保证所有找到的回文串都是奇数长度的
        for (int i = 0; i < len; ++i) {
            sb.append(s.charAt(i)).append('#');
        }
//        设置哨兵，到了边界就一定会不相等，从而结束循环
        sb.append('%');
        len = sb.length();
//        用 radius[i] 来表示以 sb 的第 i 位为回文中心，可以拓展出的最大回文半径
        int[] radius = new int[len];
//        维护 当前最靠右的回文右端点 maxRight , 以及这个回文右端点对应的回文中心 maxMid
        int maxMid = 0;
        int maxRight = 0;
        int rs = 0;
//        剪枝
        for (int currMid = 2; currMid < len - 2; currMid++) {
//            radius[currMid] = [maxRight - currMid, radius[currMid 关于 maxMid 对称点]]
//            currMid 在当前最大回文子串内：
//              回文串的性质，关于回文中心对称的两边一样，因此当前点的回文半径至少是对称点的回文半径
//              因此 currMid 处的 回文半径 最小为 对称点的最大回文半径
//                特殊情况：currMid + 对称点的最大回文半径 > maxRight
//                此时无法取到整个对称点的最大回文半径 , 但最小可以是 currMid 到 maxRight 之间
//            currMid 不在当前最靠右的回文串内：
//              以 currMid 为中心 1 为回文半径
            radius[currMid] = currMid <= maxRight ? Math.min(maxRight - currMid + 1, radius[2 * maxMid - currMid]) : 1;
//            中心拓展
            while (sb.charAt(currMid + radius[currMid]) == sb.charAt(currMid - radius[currMid])) {
                radius[currMid]++;
            }
//            动态维护 maxMid 和 maxRight
//            当前回文右端点 = 当前中心 + 最大回文半径 - 1 > 最大回文右端点
            if (currMid + radius[currMid] - 1 > maxRight) {
                maxMid = currMid;
                maxRight = currMid + radius[currMid] - 1;
            }
//            最长回文子串的结尾一定是 '#' , 因为如果结尾是有实际意义的字符，其两端一定都是 '#'
//            中心位置如果是 '#' 则半径为偶数
//            # a # b [#] b # a #   此时回文半径为 4 , 4 >> 1 == 2
//            如果为实际意义的字符则半径为奇数向下取整
//            # a # b # [currMid] # b # a #   此时回文半径为 5 , 5 >> 1 == 2
            rs += radius[currMid] >> 1;
        }
        return rs;
    }
```

## 中心扩散

```java
/**
     * 中心扩散
     */
    public int countSubstrings2(String s) {
        int rs = 0;
        int len = s.length();
//        对于一个长度为n的字符串，可以用它的任意一个字符当做中心点，所以中心点的个数是n。
//        还可以用它任意挨着的两个字符当做中心点，所以中心点是n-1，总的中心点就是2*n-1。
        for (int mid = 0; mid < (len << 1) - 1; mid++) {
            int left = mid >> 1;
            int right = left + (mid & 1);
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                rs++;
                left--;
                right++;
            }
        }
        return rs;
    }

public int countSubstrings3(String s) {
        int rs = 0;
        int len = s.length();
        for (int mid = 0; mid < len; mid++) {
            int left = mid;
            int right = mid;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                rs++;
                left--;
                right++;
            }
        }
        for (int mid = 0; mid < len; mid++) {
            int left = mid;
            int right = mid + 1;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                rs++;
                left--;
                right++;
            }
        }
        return rs;
    }
```

最后修改：2023 年 01 月 21 日