LeetCode_字符串_中等_647.回文子串

柔光的暖阳◎ 2023-10-06 22:46 64阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。  
**回文字符串是正着读和倒过来读一样的字符串。**  
子字符串是字符串中的由连续字符组成的一个序列。  
**具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。**

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

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

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

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

## 2.思路 ##

（1）中心拓展  
思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_动态规划\_中等\_5.最长回文子串][LeetCode_5.]  
[LeetCode\_回溯\_动态规划\_中等\_131.分割回文串][LeetCode_131.]  
[LeetCode\_双指针\_简单\_234.回文链表][LeetCode_234.]  
[LeetCode\_贪心算法\_简单\_409.最长回文串][LeetCode_409.]  
[LeetCode\_动态规划\_中等\_516.最长回文子序列][LeetCode_516.]  
[LeetCode\_双指针\_简单\_1332.删除回文子序列][LeetCode_1332.]

## 3.代码实现（Java） ##

//思路1————中心拓展
    class Solution {
        
        public int countSubstrings(String s) {
        
            int n = s.length();
            int res = 0;
            //遍历 n + (n - 1)  = 2 * n - 1 个回文中心
            for (int i = 0; i < 2 * n - 1; i++) {
        
                //当前的回文中心为 [left, right]，此处的 left 可以等于 right
                int left = i / 2;
                int right = i / 2 + i % 2;
                //以 [left, right] 为回文中心向左右两侧扩展
                while (left >= 0 && right < n && s.charAt(left--) == s.charAt(right++)) {
        
                    res++;
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
[LeetCode_5.]: https://blog.csdn.net/weixin_43004044/article/details/118353990
[LeetCode_131.]: https://blog.csdn.net/weixin_43004044/article/details/125341429
[LeetCode_234.]: https://blog.csdn.net/weixin_43004044/article/details/122763107
[LeetCode_409.]: https://blog.csdn.net/weixin_43004044/article/details/126935075
[LeetCode_516.]: https://blog.csdn.net/weixin_43004044/article/details/126813021
[LeetCode_1332.]: https://blog.csdn.net/weixin_43004044/article/details/127058795