【LeetCode 647】回文子串

快来打我* 2022-11-29 03:10 133阅读 0赞

#### 题目描述 ####

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

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

示例 1：

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

示例 2：

输入："aaa"
    输出：6
    解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

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

#### 解题思路 ####

这个题目使用暴力方法解决的，遍历每一种可能，具体思路如下：

*  首先，根据题目，我们可以看出，每个元素自身也算是一个回文子串，所以要将字符串的长度加进去
 *  定义一个函数用来检测字符串是否是回文串
 *  两层遍历字符串，截取字符串的所有的子串，并判断其是否是回文串

这种解题方式的时间复杂度为O(n2)，空间复杂度为O(1)

#### 代码实现 ####

/** * @param {string} s * @return {number} */
    var countSubstrings = function(s) { 
        let count = s.length
        let len = s.length
        for(let i = 0; i < len; i++){ 
            for(let j = i + 1; j < len; j++){ 
                let temp = s.substr(i, j-i+1)
                if(isSub(temp)){ 
                    count++
                }
            }
        }
        return count
    };
    const isSub = str => { 
            let a = 0
            let b = str.length - 1
            while(a <= b){ 
                if(str[a] !== str[b]){ 
                    return false
                }
                a++
                b--
            }
            return true
        }

#### 提交结果 ####

![在这里插入图片描述][20200819003230608.png]

[20200819003230608.png]: /images/20221124/74f57fcd638149c5ae0086f5e7975175.png?

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-647. 回文子串

目录动态规划题目来源 [647. 回文子串][647.] 动态规划 1.确定dp数组（dp table）以及下标的含义看回文串的性

逃离我推掉我的手/ 2024年03月24日 12:57/ 0 赞/ 61 阅读

相关 647.回文子串

647.回文子串题干分析解题思路 1. 确定dp数组（dp table）以及下标的含义 2. 确定递推公式 3.

冷不防/ 2024年03月01日 08:12/ 0 赞/ 20 阅读

相关 LeetCode_字符串_中等_647.回文子串

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。回文字符串是

柔光的暖阳◎/ 2023年10月06日 22:46/ 0 赞/ 11 阅读

相关 647. 回文子串

题目： [647. 回文子串][647.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_tex

红太狼/ 2022年12月02日 12:20/ 0 赞/ 176 阅读

相关【LeetCode 647】回文子串

题目描述给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。示例 1：

快来打我*/ 2022年11月29日 03:10/ 0 赞/ 134 阅读

相关 647. 回文子串

> 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 > > 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 > > >

亦凉/ 2022年10月16日 10:25/ 0 赞/ 135 阅读

相关【LeetCode】647. 回文子串

题目链接：[https://leetcode-cn.com/problems/palindromic-substrings/description/][https_leetco

向右看齐/ 2022年05月03日 00:56/ 0 赞/ 172 阅读

相关 LeetCode647——回文子串

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

╰+攻爆jí腚メ/ 2022年01月23日 06:25/ 0 赞/ 187 阅读

相关 647: 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。示例 1: 输入: "a

怼烎@/ 2021年10月29日 11:50/ 0 赞/ 296 阅读

相关 LeetCode :647. Palindromic Substrings 回文子串数量

试题 Given a string, your task is to count how many palindromic substrings in this strin

落日映苍穹つ/ 2021年06月24日 16:11/ 0 赞/ 349 阅读