leetcode 回文子字符串的个数_回文子串个数 leetcode

题目链接
思路一：动态规划
dp[i][j]:表示从i到j是否是一个回文串
假设dp[i][j]是一个回文串，那么dp[i+1][j-1]肯定也是一个回文串（i+1<j-1）
首先初始化dp，首先长度为1的字符串肯定是回文，所以dp[x][x]=true；
长度为2的只有第i个元素等于第i+1，dp[i][i+1]=true
后面就开始for循环，进程状态转移。
代码：

class Solution {
    public int countSubstrings(String s) {
        int slen = s.length();
        boolean[][] dp = new boolean[slen][slen];

        int res = 0;
		//长度为1的一定是
        for(int i = 0 ; i < slen;i++){
            res++;
            dp[i][i] = true;
        }

		//长度为2的只有左边的等于右边的，一定也是
        for(int i = 1 ; i < slen;i++){
            if(s.charAt(i-1)==s.charAt(i)){
                res++;
                dp[i-1][i] = true;
            }
        }
		
		//从长度为3的开始进行动态转移
        for(int len = 3; len <= slen;len++){
            for(int i = 0;i +len<=slen;i++){
            	//最左边等于最右边    并且中间是回文
                if(s.charAt(i)==s.charAt(i+len-1) && dp[i+1][i+len-2]){
                    res++;
                    dp[i][i+len-1] = true;
                }
            }
        }
        return res;
    }
}
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

思路二：对称思想
分析：如果是回文，那么串肯定是对称的。那就有对称中心，如果串长度是奇数，那么对称中心就是一个字母，如果长度是偶数，那么中心就是两个字母。
分别讨论：
奇数：以每一位当作中心，扩散，计算回文的个数
偶数：以每两个相邻的并且相同的当作中心，扩散，计算回文的个数。
代码：

class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        //奇数，以s[i]为中心扩散
        for(int i = 0;i < s.length();i++){
        	//r表示半径，半径为1 就是只有自己
            for(int r = 1; i-r+1>=0 && i+r-1<s.length();r++){
                if(s.charAt(i-r+1)==s.charAt(i+r-1)){
                    res++;
                }else{
                    break;
                }
            }
        }
        //偶数，以s[i-1]和s[i]为中心
        for(int i=1;i < s.length();i++){
            if(s.charAt(i-1)!=s.charAt(i)){
                continue;
            }
            for(int r = 1;i-r>=0&&i+r-1<s.length();r++){
                if(s.charAt(i-r)==s.charAt(i+r-1)){
                    res++;
                }else{
                    break;
                }
            }
        }
        return res;
    }
}
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