您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【LeetCode】回文子字符串的个数

题目描述

给定一个字符串 s ,请计算这个字符串中有多少个回文子字符串。

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

示例

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

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

方法:动态规划

判断一个字符串是不是回文字符串,既要满足两点:

  1. 当前字符串长度为1时,肯定是回文串;
  2. 确定两端的字符是否相等: s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]
  3. 抛去两端字符后,内部是否是回文字符串: s [ i − 1 ] = = s [ j + 1 ] s[i-1] == s[j+1] s[i1]==s[j+1]

这里在判断条件二时, s [ i − 1 ] = = s [ j + 1 ] s[i-1] == s[j+1] s[i1]==s[j+1]的结果需要已经计算出来,因此需要确定动态规划的方向。
方向确定:从下往上(i),从左往右(j)。(这样确定一个字符串是回文串的时候,条件二就已经计算出来了)

这里需要注意的是,初始化时,对创建的n * n 的二维矩阵进行False初始化。实际上我们只计算了二维数组右上角一半的值。代码如下:

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        ans = [ [False] * n for _ in range(n)]
        res = 0
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 1 or ans[i+1][j-1]:
                        res += 1
                        ans[i][j] = True
        return res

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进