647. 回文子串

解法一：暴力求解

一开始没想到什么好的思路，直接暴力求解，判断每一个子串。

class Solution {
    public int countSubstrings(String s) {
        // 长度为1的都是
        int ans = s.length();
        for (int len = 2; len <= s.length(); ++len) {
            for (int i = 0; i <= s.length() - len; ++i) {
                if (judge(s.substring(i, i + len))) {
                    ++ans;
                }
            }
        }
        return ans;
    }
    private boolean judge(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; ++i) {
            if (s.charAt(i) != (s.charAt(len - i - 1))) {
                return false;
            }
        }
        return true;
    }
}

解法二：中心扩散法

回文串的中心要么为某个字符，要么介于相邻两个字符之间，共有N*2-1种选择。然后从中心分别向两边扩展，得出以以中心为中心的最长回文子串的长度。

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        for (int i = 0; i < 2 * s.length() - 1; ++i) {
            ans += move(s, i >> 1, (i + 1) >> 1);
        }
        return ans;
    }
    /**
     * 以两个指针的位置为起始向两边移动，求扩散过程中的回文子串数量
     *
     * @param s     源字符串
     * @param left  左侧起始点下标
     * @param right 右侧起始点下标
     * @return 扩散过程中的回文子串数量
     */
    private int move(String s, int left, int right) {
        int len = s.length();
        int ans = 0;
        while ((left >= 0) && (right < len)) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            ++ans;
            --left;
            ++right;
        }
        return ans;
    }
}

解法三：动态规划

DP[i][j]表示[i, j]这个区间的子串是否为回文串,则有如下DP方程。

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        int n = s.length();
        boolean[][] flag = new boolean[n][n];
        int i, j;
        for (i = n - 1; i >= 0; --i) {
            for (j = n - 1; j >= i; --j) {
                if (i == j) {
                    flag[i][j] = true;
                } else if (s.charAt(i) == s.charAt(j)) {
                    if ((j - i) == 1) {
                        flag[i][j] = true;
                    } else {
                        flag[i][j] = flag[i + 1][j - 1];
                    }
                } else {
                    flag[i][j] = false;
                }
                if (flag[i][j]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

解法四：马拉车算法

马拉车算法参考：https://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html
官方题解：https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode/

class Solution {
    public int countSubstrings(String s) {
        int len = 2 * s.length() + 3;
        char[] chars = new char[len];
        chars[0] = '$';
        chars[len - 1] = '@';
        int index = 1;
        for (char ch:s.toCharArray()) {
            chars[index++] = '#';
            chars[index++] = ch;
        }
        chars[index] = '#';
        // 中心下标
        int center = 0;
        // 右边界下标（不包括）
        int right = 0;
        // 以下标i为中心的最长回文子串半径
        int[] Z = new int[len];
        for (int i = 1; i < len - 1; ++i) {
            if (i < right) {
                Z[i] = Math.min(Z[2 * center - i], right - i);
            }
            while (chars[i + Z[i] + 1] == chars[i - Z[i] - 1]) {
                    ++Z[i];
            }
            if (i + Z[i] > right) {
                right = i + Z[i];
                center = i;
            }
        }
        int ans = 0;
        for (int i : Z) {
            ans += (i + 1) / 2;
        }
        return ans;
    }
}