美文网首页
LeetCode 647. 回文子串

LeetCode 647. 回文子串

作者: 草莓桃子酪酪 | 来源:发表于2022-08-16 05:29 被阅读0次
题目

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

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

方法:动态规划
  • dp[i][j] 表示下标为 [i, j] 组成的字符串是否为回文串,True 表示为回文串,False 表示不为回文串
  • result 表示回文子串的数量
  • 外部循环为从下到上的循环,内部循环为从左到右的循环
    • 若首尾字符不同,那么一定不为回文串
    • 若首尾字符相同,那么需要继续判断:若 i=j,即此时只有一个字符(e.g. a),那么一定为回文串;若 j-i=1,即只有两个字符且相等(e.g. aa),那么一定为回文串;若 j-i>1,即首尾字符间存在其他字符,那么此时应判断下标为 [i+1, j-1] 组成的字符串是否为回文串,即 dp[i+1][j-1]
class Solution(object):
    def countSubstrings(self, s):
        dp = [[False] * len(s) for row in range(len(s))]
        result = 0
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j - i <= 1:
                        dp[i][j] = True
                        result += 1
                    elif dp[i+1][j-1]:
                        dp[i][j] = True
                        result += 1
        return result
参考

代码相关:https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html

相关文章

  • 两道回文子串的解法

    两道题分别是:leetcode 5. 最长回文子串 和 647. 回文子串 先看647题 找到一个字符串中所有的回...

  • LeetCode 647. 回文子串

    题目 给你一个字符串 s ,请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子...

  • # 647. 回文子串(647. Palindromic Sub

    题目地址:647. 回文子串Given a string, your task is to count how m...

  • Leetcode每日一题(5)

    647. 回文子串 给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串...

  • 647.回文子串

    647.回文子串 给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即...

  • 647. 回文子串

    思路:直接暴力来列举出所有的回文中心,然后一个一个的去判断是不是能构成回文串判断索引为left和right的值是不...

  • 647. 回文子串

    给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组...

  • 647. 回文子串

    这道题目和求解最长回文子串的题目是一样的框架结构, 不同的地方在于这到题目统计的是总数.

  • 647. 回文子串

    解法 动态规划解法 中心扩展思想

  • 647. 回文子串

    一 题目: 二 思路: 动态规划法 状态:dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。状...

网友评论

      本文标题:LeetCode 647. 回文子串

      本文链接:https://www.haomeiwen.com/subject/ecmcgrtx.html