专栏首页木又AI帮【leetcode刷题】T84-回文子串

【leetcode刷题】T84-回文子串

【题目】

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

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

示例 :

输入: "abc"
输出: 
解释: 三个回文子串: "a", "b", "c".
示例 :

输入: "aaa"
输出: 
说明: 个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

输入的字符串长度不会超过1000。

【思路】

回文串的定义是:字符串的正序和逆序相同。

暴力破解:得到所有子串,判断其是否为回文数。时间复杂度非常高。

在优化解法前,最好明白【T59-最长回文子串】的解法。

对于回文串,有"bab"和"baab"两种模式,第一种模式只有一个中心,第二种模式有两个中心。

我们遍历每个元素,以该元素s[i]为中心找到所有回文串,再以s[i]和s[i+1]为双中心找到所有回文串。进行计数即可得到答案。

【代码】

python版本

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)
        # 单字符都是回文字符串
        count = length
        for i in range(length):
            # s[i]为回文串唯一中心
            for j in range(, length):
                if i-j >=  and i+j < length and s[i-j] == s[i+j]:
                    count += 
                else:
                    break
            # s[i]和s[i+1]为回文串双中心
            for j in range(, length):
                if i+-j >=  and i+j < length and s[i+-j] == s[i+j]:
                    count += 
                else:
                    break
        return count

C++版本

class Solution {
public:
    int countSubstrings(string s) {
        int length = s.size();
        // 所有单字符都是回文串
        int count = length;
        for(int i=; i<length; i++){
            //s[i]为回文串唯一中心
            for(int j=; j<length; j++){
                if(i-j >=  && i+j < length && s[i-j] == s[i+j])
                    count++;
                else
                    break;
            }
            //s[i]和s[i+1]为回文串双中心
            for(int j=; j<length; j++){
                if(i+-j >=  && i+j < length && s[i+-j] == s[i+j])
                    count++;
                else
                    break;
            }
        }
        return count;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T72-反转字符串

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

    木又AI帮
  • 【leetcode刷题】T69-解码方法

    对于1,只有1种可能,对于11,有2种可能(1 1 和11),对于111,有3种可能(1 1 1、11 1、1 11),对于1111,有5种可能(1 1 1 1...

    木又AI帮
  • 【leetcode刷题】T185-回文数

    https://leetcode-cn.com/problems/palindrome-number

    木又AI帮
  • JAVA全栈开发微服务架构模式 顶

    对于微内核的架构而言主要是把服务进行拆分,每个微服务都是可以独立运行的,所以我们采用Nutz+嵌入式Jetty的模式进行搭建,这样直接在命令行下就可以独立启动了...

    bdcn
  • 【LeetCode题解-009】Palindrome Number

    Determine whether an integer is a palindrome. An integer is a palindrome when it...

    周三不加班
  • Hive 3的ACID表

    您可以创建ACID(原子性,一致性,隔离性和持久性)表用于不受限制的事务或仅插入的事务。这些表是Hive托管表。数据与Schema一起位于Hive metast...

    大数据杂货铺
  • 最长子字符串

    1、 第一种方式,时间复杂度 n3,这种方式在实际情况下是不可取的。 2、时间复杂度:O(2n) = O(n)O(2n)=O(n),在最糟糕的情况下,每个字符...

    OPice
  • No.005 Longest Palindromic Substring

    5. Longest Palindromic Substring Total Accepted: 120226 Total Submissions: 50952...

    mukekeheart
  • 特斯拉炫技现场:电驴、行人、快递车,中国的小路难不倒Autopilot自动驾驶

    这是想让全球的人类知道,有了Autopilot便能更加放心安全地驾驶,即便是要应付我国的神秘路况。

    量子位
  • MySQL事务最全详解

    记得前些日子分享过一篇有关MySQL中事务的知识点,但当时对MySQL中的事务只是纯粹的知道如何使用,缺乏对理论的进一步认识,抽时间单独去了解了一下,便在做一个...

    A梦多啦A

扫码关注云+社区

领取腾讯云代金券