回文子串数量

中心扩展算法

import java.util.*;


public class Solution {
  /**
   * 
   * @param str string字符串 
   * @return int整型
   */
  public int palindromeCount (String str) {
    int ans = 0;
    for (int center = 0; center < str.length(); center++) {
      ans += expand(str, center, center) + expand(str, center, center + 1);
    }
    return ans;
  }

  private int expand(String str, int left, int right) {
    int ans = 0;
    while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
      ans++;
      left--;
      right++;
    }
    return ans;
  }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param str string字符串 
     * @return int整型
     */
    public int palindromeCount (String str) {
        char[] cs = str.toCharArray();
        int res = 0;
        int n = str.length();
        boolean[][] f = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) {
                    f[i][j] = true; 
                } else if (i + 1 == j) {
                    f[i][j] = cs[i] == cs[j];
                } else {
                    f[i][j] = f[i + 1][j - 1] && cs[i] == cs[j];
                }
                if (f[i][j]) {
                    res++;
                }
            }
        }
        return res;
    }
}

   public static int getHuiWenNumber(String str){
        int number=0;
        for(int i=0;i<str.length();i++){
            for(int left=i,right =i;left>=0 &&right<str.length();left--,right++){
                if(str.charAt(left)!=str.charAt(right)){
                    break;
                }
                number++;
            }
        }
        return number;
    }

    public static Integer palindromeNum(String str) {
        int num = 0;
        if (StringUtils.isNotBlank(str)) {
            int index = 0;
            int nextIndex;
            while (index < str.length()) {
                nextIndex = str.indexOf(str.charAt(index), index + 1);
                if (nextIndex == -1 || !isPalindrome(str.substring(index, nextIndex + 1))) {
                    index++;
                    continue;
                } else {
                    num++;
                }
                index = nextIndex;
            }
        }
        return num;
    }

    public static Boolean isPalindrome(String str) {
        if (StringUtils.isNotBlank(str) && str.length() > 1) {
            char[] chars = str.toCharArray();
            for (int i = 0; i < str.length() / 2; i++) {
                if (chars[i] != chars[str.length() - i - 1]) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }