( 字符串) 647. 回文子串 ——【Leetcode每日一题】

news/2024/2/28 10:51:55

❓647. 回文子串

难度:中等

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

💡思路:

法一:暴力

两层for循环,遍历区间起始位置和终止位置,然后判断这个区间是不是回文。

时间复杂度: O ( n 3 ) O(n^3) O(n3)

法二:中心扩展法

从字符串的某一位置为中心,尝试着在两边扩展子字符串。

  • 可以是奇数长度,也可以是偶数长度。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

法三:动态规划

这一题还可以使用动态规划来进行解决:

  • 状态:dp[i][j] 表示字符串s[i, j]区间的子串是否是一个回文串。
  • 状态转移方程:当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时,dp[i][j] = true,否则为false

在这里插入图片描述

这个状态转移方程是什么意思呢?

  1. 如果s[i] != s[j]必然不是回文串,所以下面的前提都为s[i] == s[j];
  2. 当只有一个字符时,比如 a 自然是一个回文串; 以及当有两个字符时,如果是相等的,比如 aa,也是一个回文串,所以设置j - i < 2,是回文字符串;
  3. 当有三个及以上字符时,比如 lol 这个字符记作串,把两边的 l 去掉,也就是 o , 如果o为回文串,那么 lol 也一定是回文串。所以当 s[i]==s[j] 时,自然要看 dp[i+1][j-1] 是不是一个回文串。

🍁代码:(Java、C++)

法一:暴力
Java

class Solution {public int countSubstrings(String s) {int n = s.length();int cnt = n;for(int len = 2; len <= n; len++){for(int i = 0; i + len <= n; i++){cnt += isPlim(s.substring(i, i + len)) ? 1 : 0;}}return cnt;}public boolean isPlim(String s){for(int i = 0, j = s.length() - 1; i < j ; i++, j--){if(s.charAt(i) != s.charAt(j)) return false;}return true;}
}

C++

class Solution {
public:int countSubstrings(string s) {int n = s.size();int cnt = n;for(int len = 2; len <= n; len++){for(int i = 0; i + len <= n; i++){cnt += isPlim(s.substr(i, len)) ? 1 : 0;}}return cnt;}bool isPlim(string s){for(int i = 0, j = s.size() - 1; i < j; i++, j--){if(s[i] != s[j]) return false;}return true;}
};

法二:中心扩展法
Java

class Solution {private int cnt = 0;public int countSubstrings(String s) {for (int i = 0; i < s.length(); i++) {extendSubstrings(s, i, i);     // 奇数长度extendSubstrings(s, i, i + 1); // 偶数长度}return cnt;}private void extendSubstrings(String s, int start, int end) {while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {cnt++;start--;end++;}}
}

C++

class Solution {
public:int cnt = 0;int countSubstrings(string s) {for(int i = 0; i < s.size(); i++){extendSubstr(s, i, i);     //奇数长度extendSubstr(s, i, i + 1); //偶数长度}return cnt;}void  extendSubstr(string s, int start, int end){while(start >= 0 && end < s.size() && s[start] == s[end]){cnt++;start--;end++;}}
};

法三:动态规划
Java

class Solution {public int countSubstrings(String s) {boolean[][] dp = new boolean[s.length()][s.length()];int cnt = 0;for (int j = 0; j < s.length(); j++) {for (int i = 0; i <= j; i++) {if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {dp[i][j] = true;cnt++;}}}return cnt;}
}

C++

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int cnt = 0;for (int j = 0; j < s.size(); j++) {for (int i = 0; i <= j; i++) {if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {dp[i][j] = true;cnt++;}}}return cnt;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 n 为字符串的长度,中心扩展法动态规划 O ( n 2 ) O(n^2) O(n2)。。
  • 空间复杂度 O ( 1 ) O(1) O(1)暴力中心扩展法的空间复杂度是 O ( 1 ) O(1) O(1)动态规划 O ( n 2 ) O(n^2) O(n2)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/58206.html

相关文章

字节跳动发放年终奖,远超预期~

最近一段时间&#xff0c;国内互联网大厂接连公布年终奖情况&#xff0c;整个后厂村都洋溢在春节般的喜庆气氛里。 虽然由于各种各样的顾虑&#xff08;主要是人员流失问题&#xff09;&#xff0c;大部分公司都将年终奖发放时间调整到了年中&#xff0c;但好饭不怕晚&#xf…

C语言选择语句

在C语言中&#xff0c;选择语句是程序控制流程的重要部分之一。选择语句可以根据指定的条件进行分支判断&#xff0c;并根据判断结果执行相应的代码。C语言中的选择语句主要包括if语句、if-else语句、nested if语句和switch-case语句。接下来将会对这些语句进行详细介绍。 if语…

3.1 存储系统概述

学习目标&#xff1a; 以下是一个关于存储系统概述的具体学习目标&#xff1a; 理解计算机存储器的基本概念&#xff0c;包括存储器的分类、存储单元、存储器容量等基本概念。 掌握存储器的存取原理&#xff0c;包括地址结构、存取周期、存取速度等相关概念。 熟悉常见的存储…

网络工程师 - 面试手册

网络工程师 - 面试手册 岗位概述 网络工程师主要负责企业或组织的网络基础设施建设、维护和优化。他们需要确保网络的稳定运行&#xff0c;以支持组织内部的通信和业务需求。网络工程师通常需要掌握计算机网络原理、网络设备配置和故障排除等方面的知识。 常见的职位招聘描述…

TouchGFX开发(1)----安装软件

TouchGFX开发.1----安装软件 概述TouchGFX 特点下载&安装 概述 TouchGFX 是一个高性能的嵌入式图形库&#xff0c;主要用于为微控制器&#xff08;MCU&#xff09;驱动的设备创建现代用户界面&#xff08;UI&#xff09;。它提供了一套丰富的图形功能&#xff0c;使开发者…

uboot第二阶段 start_armboot函数代码分析

1.1、start_armboot函数简介 这个函数整个构成了uboot启动的第二阶段。 1.2、uboot第二阶段做的事情 uboot第一阶段主要就是初始化了SoC内部的一些部件&#xff08;譬如看门狗、时钟、串口…&#xff09;&#xff0c;然后初始化DDR并且完成重定位。那么&#xff0c;uboot的第…

自动驾驶TPM技术杂谈 ———— I-vista验收标准(评价规程)

文章目录 介绍评价细则平行车位泊车能力评价细则垂直车位泊车能力评价细则斜向车位泊车能力评价细则 新功能评价细则平行车位远程操控泊入泊出评价细则垂直车位远程操控泊入泊出评价细则 用户手册评价 介绍 i-VISTA (Intelligent Vehicle Integrated Systems Test Area)智能汽车…

存储器(二)

目录 一、RAM 1.RAM特点 2.静态RAM 2.1静态RAM保存原理 2.2静态RAM基本单元电路的构成 2.3静态RAM读写操作 3.动态RAM 3.1动态RAM保存原理 3.2动态RAM基本单元电路的构成 3.3动态RAM对单元电路的读写操作 3.4动态RAM的刷新 4.静态RAM与动态RAM的比较 二、ROM 1.ROM…

如何理解代码覆盖率?

什么是代码覆盖率&#xff1f; 代码覆盖率&#xff08;Code coverage&#xff09;是软件测试中的一种度量&#xff0c;描述应用程序中源代码被测试的比例和程度&#xff0c;所得比例称为代码覆盖率。通常情况下&#xff0c;代码覆盖率是通过计算测试用例的执行结果与代码行数的…

为什么不要相信AI机器人提供的健康信息?

自从OpenAI、微软和谷歌推出了AI聊天机器人&#xff0c;许多人开始尝试一种新的互联网搜索方式&#xff1a;与一个模型进行对话&#xff0c;而它从整个网络上学到的知识。 专家表示&#xff0c;鉴于之前我们倾向于通过搜索引擎查询健康问题&#xff0c;我们也不可避免地会向Ch…

python+django+vue消防知识宣传网站

开发语言&#xff1a;Python 框架&#xff1a;django Python版本&#xff1a;python3.7.7 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;PyCharm 层随着移动应用技术的发展&#xff0c;越来越多的消防单位借助于移动手机、电脑完成生活中的事…

spring5源码篇(9)——mybatis-spring整合原理

spring-framework 版本&#xff1a;v5.3.19 spring和mybatis的整合无非主要就是以下几个方面&#xff1a; 1、SqlSessionFactory怎么注入&#xff1f; 2、Mapper代理怎么注入&#xff1f; 3、为什么要接管mybatis事务&#xff1f; 文章目录 一、SqlSessionFactory怎么注入SqlSe…

《基于EPNCC的脉搏信号特征识别与分类研究》阅读笔记

目录 一、论文摘要 二、论文十问 三、论文亮点与不足之处 四、与其他研究的比较 五、实际应用与影响 六、个人思考与启示 参考文献 一、论文摘要 为了快速获取脉搏信号的完整表征信息并验证脉搏信号在相关疾病临床诊断中的敏感性和有效性。在本文中&#xff0c;提出了一…

前端开发工程师 - 面试手册

前端开发工程师 - 面试手册 岗位概述 前端开发工程师负责构建和维护网站或Web应用的用户界面。他们使用HTML、CSS和JavaScript等编程语言&#xff0c;实现网页的布局、样式和交互功能。前端开发工程师需要与UI/UX设计师、后端开发人员以及产品经理密切合作&#xff0c;共同打…

【LeetCode股票买卖系列:309. 最佳买卖股票时机含冷冻期 | 暴力递归=>记忆化搜索=>动态规划】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

Contest3111 - 计科2101~2104算法设计与分析上机作业07

问题 A: 有重复元素的排列问题 题目描述 设R{ r 1 , r 2 , …, r n }是要进行排列的n个元素。其中元素r 1 , r 2 , …, r n 可能相同。试设计一个算法&#xff0c; 列出R的所有不同排列。给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。 输入 第1 行是元素个…

程序员 2023年的5个方向

2023年了 跟大家聊聊2023年及以后 我们程序员后端就开发这个行业 这个方向它大概是什么样 首先 我在网上上看到很多这种知识博主 包括很多这种机构号 我不知道大家有没有感受到一个点 IT已经变成一个越来越高门槛的一个 工种了就作为一个开发者 如果未来你最低学历 可能就是要一…

对云计算的简单理解

云计算作为思考问题的新方式&#xff0c;基于联系和交互以及在扩展时的连带性&#xff0c;既考虑安全&#xff0c;又考虑性能。   没有必要做什么系统都要来个翻天覆地地变化&#xff0c;从细微处做起&#xff0c;从现在做起&#xff0c;云要运行于平台之上&#xff0c;而平台…

PAT A1012 The Best Rank

1012 The Best Rank 分数 25 作者 CHEN, Yue 单位 浙江大学 To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C - C Programming Language, M - Mathematics (Calculus or Linear Algrbra), and E -…

《*** 经济思想学习纲要》学习辅导

《*** 经济思想学习纲要》学习辅导 单选题&#xff08;共7题&#xff0c;每题5分&#xff09; 1、&#xff08;&#xff09;是现代化的最大“拦路虎”。 正确答案&#xff1a;B、中等收入陷阱 2、进入新发展阶段&#xff0c;是我国经济发展的&#xff08;&#xff09;。 正确答…
最新文章