当前位置: 首页 > news >正文

【LeetCode每日一题】——680.验证回文串 II

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目示例】
  • 六【解题思路】
  • 七【题目提示】
  • 八【时间频度】
  • 九【代码实现】
  • 十【提交结果】

一【题目类别】

  • 贪心算法

二【题目难度】

  • 简单

三【题目编号】

  • 680.验证回文串 II

四【题目描述】

  • 给你一个字符串 s,最多 可以从中删除一个字符。
  • 请你判断 s 是否能成为回文字符串:如果能,返回 true ;否则,返回 false 。

五【题目示例】

  • 示例 1:

    • 输入:s = “aba”
    • 输出:true
  • 示例 2:

    • 输入:s = “abca”
    • 输出:true
    • 解释:你可以删除字符 ‘c’ 。
  • 示例 3:

    • 输入:s = “abc”
    • 输出:false

六【解题思路】

  • 利用贪心算法的思想,由外到内逐层判断是否是回文串
  • 要判断一个字符串是不是回文串,可以从外面开始判断,只有两种情况:
    • 第一个字符和最后一个字符相等,那么只需要判断里面的其余字符
    • 第一个字符和最后一个字符不相等,那么这个字符串就不是回文串,根据题目要求,可以去掉第一个字符或者最后一个字符再次进行判断,但是需要注意的是,只能删除一次
  • 根据以上思路,我们首先从最外层开始判断,如果没发现有对应位置不相等的字符就判断是一个回文串
  • 如果发现有对应位置不相等的字符,去掉最左边或者最右边的字符再进行一次是否是回文串的判断,如果还有对应位置不相等的字符,肯定就不满足题意了,返回false即可,如果没有对应位置不相等的字符,返回true即可

七【题目提示】

  • 1<=s.length<=1051 <= s.length <= 10^51<=s.length<=105
  • s由小写英文字母组成s 由小写英文字母组成s由小写英文字母组成

八【时间频度】

  • 时间复杂度:O(n)O(n)O(n),其中nnn为传入字符串长度
  • 空间复杂度:O(1)O(1)O(1)

九【代码实现】

  1. Java语言版
class Solution {public boolean validPalindrome(String s) {int left = 0;int right = s.length() - 1;while(left < right){if(s.charAt(left) != s.charAt(right)){return isPalindrome(s,left + 1,right) || isPalindrome(s,left,right - 1);}left++;right--;}return true;}public boolean isPalindrome(String s,int i,int j){while(i < j){if(s.charAt(i) != s.charAt(j)){return false;}i++;j--;}return true;}
}
  1. C语言版
bool isParlindrome(char *s,int i,int j)
{while(i < j){if(s[i] != s[j]){return false;}i++;j--;}return true;
}bool validPalindrome(char * s)
{int left = 0;int right = strlen(s) - 1;while(left < right){if(s[left] != s[right]){return isParlindrome(s,left + 1,right) || isParlindrome(s,left,right - 1);}left++;right--;}return true;
}
  1. Python版
class Solution:def validPalindrome(self, s: str) -> bool:def isPalindrome(i,j):while i < j:if s[i] != s[j]:return Falsei += 1j -= 1return Trueleft = 0right = len(s) - 1while left < right:if s[left] != s[right]:return isPalindrome(left + 1,right) or isPalindrome(left,right - 1)left += 1right -= 1return True

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. C语言版
    在这里插入图片描述

  3. Python语言版
    在这里插入图片描述

http://www.lryc.cn/news/30634.html

相关文章:

  • 【C语言进阶:指针的进阶】你真分得清sizeof和strlen?
  • 【前端必看】极大提高开发效率的网页 JS 调试技巧
  • 【春招面经】视源股份前端一面
  • 插件化开发入门
  • tftp、nfs 服务器环境搭建
  • 汇编系列03-不借助操作系统输出Hello World
  • TPU编程竞赛系列|算能赛道冠军SO-FAST团队获第十届CCF BDCI总决赛特等奖!
  • 【C++】AVL树,平衡二叉树详细解析
  • C/C++开发,无可避免的多线程(篇四).线程与函数的奇妙碰撞
  • elisp简单实例: taglist
  • Azure AI基础到实战(C#2022)-认知服务(3)
  • aws apigateway 使用restapi集成lambda
  • HTML基础
  • ThreadPoolExecutor参数 keepAliveTime allowCoreThreadTimeOut
  • 什么是Hibernate框架?
  • 指针面试笔试题练习
  • docker(三)仓库的搭建、官方私有仓库的加密和认证
  • FPGA实现SDI视频编解码 SDI接收发送,提供2套工程源码和技术支持
  • Android 基础知识4-3.5 RadioButton(单选按钮)Checkbox(复选框)详解
  • 用代码实现解析解的方式求解_梯度下降法思路_导函数有什么用_接23节---人工智能工作笔记0026
  • 大数据ETL开发之图解Kettle工具
  • docker-容器数据卷
  • 【C++】类和对象补充知识点
  • 路径规划-人工势场法
  • 20230304学习笔记
  • [数据集][VOC][目标检测]河道垃圾水面漂浮物数据集目标检测可用yolo训练-1304张介绍
  • JavaWeb--JSP案例
  • 推荐系统1--Deepfm学习笔记
  • javaDoc生成方式
  • Armv9 registers