647. Palindromic Substrings

Question

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Solution

Manacher算法，与5. Longest Palindromic Substring的实现方法相同。

首先处理字符串。
然后采用中心拓展计算各个位置的拓展长度，并维护c与r。
每次遍历时计算结果，将当前可扩展长度加一然后除以二后加入结果。

Code

class Solution {
    int n;
    int[] p;
    String newString;
    public int countSubstrings(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        
        return manacher();
    }
    
    private int manacher(){
        int res = 0, c = 0, r = 0;
        for(int i = 1; i < newString.length()-1; i++){
            int m = 2 * c - i;
            if(i < r) p[i] = Math.min(r-i, p[m]);
            
            while(newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)){    //中心拓展
                p[i]++;
            }
            
            if(i+p[i] > r){ //更新c与r
                c = i;
                r = i + p[i];
            }
            res += (p[i]+1)/2;  //向上取整
        }
        return res;
    }
}

Solution 2

中心拓展，辅助方法count()用来计算每个字符可以组成的最大回文数。

注意每次需要计算奇数长度回文和偶数长度回文两种情况。
遍历所有字符并加和，返回总数。

Code

class Solution {
    String word;
    public int countSubstrings(String s) {
        word = s;
        int ret = 0;
        for(int i = 0; i < s.length(); i++){
            ret+=count(i);
        }
        return ret;
    }
    
    private int count(int i){
        int count = 1, left = i-1, right = i+1;

        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        
        left = i;
        right = i+1;
        
        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        return count;
    }
}