CodeCollection2018
8/30/2019 - 12:48 PM

Palindromic Substrings--回文子串数量

给定某个字符串，求其中回文子串数量。例如“aaa”，结果就是"a", "a", "a", "aa", "aa", "aaa"，6个

brute force
content_copyfile_download
//暴力法，针对每一个字符将其作为中心向外扩展，扩展一层结果数加一，但是要考虑奇偶回文问题
public int countSubstrings(String s){
    if(s.isEmpty()) return 0;
    int n = s.length(),res=0;
    for(int i = 0; i < n; i++){
        helper(s,i,i,res);
        helper(s,i,i+1,res);
    }
    return res;
}
public void helper(String s,int i,int j,int* res){
    while(i>=0 && j <s.length() && s.charAt(i)==s.charAt(j)){
        i--,j++,res++;
    }
}