力扣刷题-最长回文子串

简介: 力扣刷题-最长回文子串

题目

给你一个字符串 s,找到 s 中最长的回文子串。

输入: s = "babad"
输出: "bab"
解释: "aba" 同样是符合题意的答案。

题解

我们这里使用一个叫做从中心扩散的思想,这个思想是指我们遍历字符串中的每一个字符,我们这里把字符串中的第二个字符a作为起点,把它当他当成一个中心,往两边扩散,并且检查它的左边和右边的字符是否相等,如果相等的话,这就是我们找到的回文字符串,然后再向两边扩散,在进行判断a字符左右两边各相隔一个字符的2字符是否相亲,如果相等在扩散,如果不相等则停止更换中心起点,以此往复,并不是所有的回文字符串都有一个中心点,有的回文字符串有中心的,有的回文字符串则没有中心点,所以我们需要处理这两种情况,首先我们写一个判断条件,判断当前传入的字符长度是否小于2,如果小于2则直接放回原字符串,在定义两个变量,start变量存储于当前找到的最大回文字符串的起始位置,maxLength记录了最大回文字符串的长度,终止位置也就是start变量加上maxLength变量,每次我们找到一个更大的回文字符串都需要更新一下start变量和maxLength变量的值,然后在创建一个helper函数,作用域判断左边和右边是否越界,越界则停止,同时判断最左边的字符串是否等于最右边的字符,如果以上三个字符的三个条件都满足,则判断是否需要更新回文字符串中最大长度以及最大字符的起始位置,然后继续向两边扩散,直到不满足三个条件之一停止,我们在进行遍历字符串时需要调用helper函数两遍,第一遍是检查中心点的左右两边的字符是否越界和是否相等,第二遍是检查中心点和右边的字符是否越界和是否相等

var longestPalindrome = function(s) {
 if(s.length<2){
     return s;
 }
 //maxLength是处理两个字符的情况,每个单个字符都可以被当做一个回文字符串,所以长度初始化为1
 let start=0,maxLength=1;
 function helper(left,right){
     while(left>=0&&right<s.length&&s[left]===s[right]){
         if(right-left+1>maxLength){
             maxLength=right-left+1
             start=left
         }
         left--;
         right++;
     }
 }
 for(let i=0;i<s.length;i++){
     helper(i-1,i+1)
     helper(i,i+1)
 }
 return s.substring(start,start+maxLength)
};
相关文章
|
3天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
11 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
2天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
10 0
|
3天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
8 0
|
3天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
13 1
|
3天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
9 0
|
3天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
8 0
|
3天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
9 0
|
6天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
12 1
|
6天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
12 0
|
15天前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
12 2