报表网站建设,263企业邮箱手机登录,专业网站建设公,微信php网站开发流程给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字符组成#xff0c;也会被视作不… 给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。 示例 1 输入s “abc” 输出3 解释三个回文子串: “a”, “b”, “c” 示例 2 输入s “aaa” 输出6 解释6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa” 提示 1 s.length 1000 s 由小写英文字母组成 计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串而枚举出所有的回文字串又有两种思路分别是 枚举出所有的子串然后再判断这些子串是否是回文 枚举每一个可能的回文中心然后用两个指针分别向左右两边拓展当两个指针指向的元素相同的时候就拓展否则停止拓展。
假设字符串的长度为 n。我们可以看出前者会用 O ( n 2 ) O(n^2) O(n2) 的时间枚举出所有的子串 s [ l i . . . r i ] s[l_i...r_i] s[li...ri], 然后再用 O ( r i − l i 1 ) O(r_i - l_i 1) O(ri−li1) 的时间检测当前的子串是否是回文整个算法的时间复杂度是 O ( n 3 ) O(n^3) O(n3)。而后者枚举回文中心的是 O ( n ) O(n) O(n) 的对于每个回文中心拓展的次数也是 O ( n ) O(n) O(n)的所以时间复杂度是 O ( n 2 ) O(n^2) O(n2)。所以我们选择第二种方法来枚举所有的回文子串。
在实现的时候我们需要处理一个问题即如何有序地枚举所有可能的回文中心我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数那么回文中心是一个字符如果回文长度是偶数那么中心是两个字符。
class Solution:def countSubstrings(self, s: str) - int:n len(s)ans 0for i in range(n):#奇数长度ans 1l, r i - 1, i 1while l -1 and r n:if s[l] s[r]:ans 1else:breakl - 1r 1#偶数长度if (i 1) n and s[i] s[i1]:ans 1l, r i - 1, i 2while l -1 and r n:if s[l] s[r]:ans 1else:breakl - 1r 1return ansif __name__ __main__:s Solution()print(s.countSubstrings(abc))print(s.countSubstrings(aaa))复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。空间复杂度 O ( 1 ) O(1) O(1)。
复杂度更低的方法参考https://leetcode.cn/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
