ps:图片源于网络侵删目录一、题目二、代码三、核心逻辑解析一、题目给定一个字符串s请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。示例 1输入s abc输出3解释三个回文子串: a, b, c示例 2输入s aaa输出6解释6个回文子串: a, a, a, aa, aa, aaa提示1 s.length 1000s由小写英文字母组成二、代码class Solution { /** * 计算字符串中回文子串的总数 * param s 输入的字符串 * return 回文子串的数量 */ public int countSubstrings(String s) { // 边界条件处理如果字符串为空或长度为0直接返回0 if (s null || s.length() 0) { return 0; } int count 0; // 初始化回文子串的计数器 // 遍历字符串的每一个字符将其作为潜在的回文中心 for (int i 0; i s.length(); i) { // 情况1以当前字符 s[i] 为单一中心奇数长度回文如 aba // 传入相同的索引 i, i 作为左右起点 count countPalindrome(s, i, i); // 情况2以当前字符 s[i] 和下一个字符 s[i1] 为双中心偶数长度回文如 abba // 传入相邻的索引 i, i1 作为左右起点 count countPalindrome(s, i, i 1); } return count; // 返回最终的统计结果 } /** * 从指定的中心位置向两边扩展统计能形成的回文子串数量 * param s 输入的字符串 * param start 扩展的左边界起始索引 * param end 扩展的右边界起始索引 * return 以该中心扩展出的回文子串数量 */ private int countPalindrome(String s, int start, int end) { int count 0; // 记录当前中心能找到的回文串个数 // 循环条件 // 1. start 0 : 左边界不能越界不能小于0 // 2. end s.length() : 右边界不能越界不能大于等于字符串长度 // 3. s.charAt(start) s.charAt(end) : 左右两边的字符必须相等 while (start 0 end s.length() s.charAt(start) s.charAt(end)) { // 只要满足上述条件说明找到了一个新的回文子串 count; // 继续向两边扩展左指针左移右指针右移 start--; end; } return count; // 返回当前中心找到的回文子串总数 } }三、核心逻辑解析为什么循环里要调用两次countPalindrome因为回文串的长度分为奇数和偶数。奇数回文如racecar有一个绝对的中心字符所以用(i, i)扩展。偶数回文如noon的中心在两个字符之间所以用(i, i1)扩展。时间复杂度 O(N2)O(N2) 。外层循环遍历 NN 个字符内层while循环在最坏情况下比如全由相同字符组成的字符串aaaaa会扩展到边界耗时 O(N)O(N) 。空间复杂度 O(1)O(1) 。只使用了几个整型变量没有使用额外的数组或哈希表。