leetcode647. Palindromic Substrings

image.png

求字符串中的回文子数组的个数

思路1：
我们以字符串中的每个元素为中心，向两边扩展，判断扩展出来的字符串是不是回文串，注意边界条件以及字符串的数量的奇偶情况

 public  int countSubstrings(String s) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            res += judge(s, i, i);
            res += judge(s, i, i + 1);
        }
        return res;
    }

    public int judge(String s, int lo, int hi) {
        int res = 0;
        while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
            lo--;
            hi++;
            res++;
        }
        return res;
    }

思路2：
Manacher's Algorithm的实现
记得对回文半径数组中的值除以2，表示原字符串中的结果

public  int countSubstrings(String s) {
        char[] newChar = manacherString(s);
        int[] pArr = new int[newChar.length];
        int index = -1, pR = -1;
        for (int i = 0; i < newChar.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (i + pArr[i] < newChar.length && i - pArr[i] > -1) {
                if (newChar[i + pArr[i]] == newChar[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
        }
        int res = 0;
        for (int num : pArr) {
            res += num / 2;
        }
        return res;
    }

    public static char[] manacherString(String s) {
        int n = s.length();
        char[] newChar = new char[2 * n + 1];
        int index = 0;
        for (int i = 0; i < newChar.length; i++) {
            newChar[i] = (i & 1) == 0 ? '#' : s.charAt(index++);
        }
        return newChar;
    }