Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

一.题目介绍

1.题目来源

链接：LeetCode

2.题目

给你一个字符串s，请你统计并返回这个字符串中回文子串的数目。

回文字符串是正着读和倒过来读一样的字符串。

子字符串是字符串中的由连续字符组成的一个序列。

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

 
示例 1：

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
 

提示：1 <= s.length <= 1000 s由小写英文字母组成

二.具体实现

1.实现思路

回文算是算法题的经典题型了，只不过是一些题目是变种了，解题的基本思路还是一样的，双层循环，逐一匹配折字符串里的元素，如果相等则是回文，不相等则继续匹配。

2.实现代码

1)自己的实现方式

public int countSubstrings(String s) {
    int res = 0;
    int n = s.length();
    // boolea[i][j] 代表 字符串从i 到 j 是不是回文串
    // 注意，外层循环要倒着写，内层循环要正着写
    // 因为要求dp[i][j] 需要知道dp[i+1][j-1]
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            // (s.charAt(i)==s.charAt(j) 时，当元素个数为1,2,3个时，一定为回文子串
            if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                res++;
            }
        }
    }
    return res;
}
复制代码

2)题友的实现方式

使用的是中心拓展的思想，枚举出所有的子串，然后再判断这些子串是否是回文，枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展，即是找到目标回文返回。

3.运行结果

三.题后思考

感觉做算法题以来，看到这种类似的题型就是循环，然后匹配，实际上时间复杂度这些没有去关注，比如这一题，题友的做法就少了一层循环，时间复杂度肯定比我的小，还是老生常谈的问题，慢慢积累吧，算法这事急不得。