509. 斐波那契数/面试题10- I. 斐波那契数列(简单)

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
注意:

​ 输入的字符串长度不会超过1000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings

思路：

和leetcode5思路一样，但是这里一个字母也算一个回文，其他没什么不同

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countSubstrings(String s) {
        
        int len = s.length();//每个长度都算一个回文,怎么将每一位都标记为true；
        //用来计数
        int count = len;
        boolean[][] dp = new boolean[len][len];
        for(int i=0;i<len;i++)
            dp[i][i] = true;
        //对比leetcode，最长回文子串
        for(int i =len-1;i>=0;i--){
            for(int j=i+1;j<len;j++){
                if(s.charAt(i)==s.charAt(j))
                    dp[i][j] = j - i ==1?true:dp[i+1][j-1];
                else
                    dp[i][j] = false;
                if(dp[i][j])
                    count++;
            }
        }
        return count;

    }
}