Palindromic Substrings

Posted on |

问题描述（难度中等）

given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

1
2
3
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won’t exceed 1000.

方法一：中心扩展法

选择中心进行扩展，中心可以分为两种情况，第一种是单个字符，第二种是两个字符。其他的情况都可以从这两种情况为中心的字符进行扩展。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package P647;

/**
 * 中心扩展法
 * @autor yeqiaozhu.
 * @date 2019-10-28
 */
public class UsingCircle {
    private String string;
    private int count;
    public int countSubstrings(String s) {
        string=s;
        for (int i = 0; i < s.length(); i++) {
            //两个元素为中心
            checkParamlings(i,i+1);
            //单个元素为中心
            checkParamlings(i,i);
        }
        return count;
    }

    public void checkParamlings(int i,int j){
        while (i>=0 && j<string.length() && string.charAt(i) == string.charAt(j)){
            count++;
            i--;
            j++;
        }
    }

    public static void main(String[] args) {
        String s="aaa";
        System.out.println(new UsingCircle().countSubstrings(s));

        String s1="abc";
        System.out.println(new UsingCircle().countSubstrings(s1));
    }
}

方法二：二维数组

二维数组保存结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package P647;

class Solution {
    boolean[][] booleans;
    public int countSubstrings(String s) {
        if (s==null || s.length()==0) {
            return 0;
        }
        booleans=new boolean[s.length()][s.length()];
        int count=0;
        //一层循环定义长度
        for (int i = 1; i <=s.length(); i++) {
            //定义
            for (int j = 0; j+i-1 < s.length(); j++) {
                if (i==1) {
                    booleans[j][j]=true;
                }else if (i==2) {
                    booleans[j][j+1] = s.charAt(j)==s.charAt(j+1);
                }else {
                    booleans[j][j+i-1]=(s.charAt(j)==s.charAt(j+i-1) && booleans[j+1][j+i-2]);
                }
                if (booleans[j][j+i-1]) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s="aaa";
        System.out.println(new Solution().countSubstrings(s));

        String s1="abc";
        System.out.println(new Solution().countSubstrings(s1));
    }
}

总结

中心扩展法思路比较简洁，可以作为算法扩展到其他的情形。