【力扣hot100】 5. 最长回文子串

张开发
• 2026/4/16 13:53:28 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【力扣hot100】 5. 最长回文子串
一、题目给你一个字符串 s找到 s 中最长的 回文 子串。 示例 1 输入s babad 输出bab 解释aba 同样是符合题意的答案。 示例 2 输入s cbbd 输出bb 提示 1 s.length 1000 s 仅由数字和英文字母组成二、思路上一题做的是三数之和这题自然而然就联想到了滑动窗口但我本质上做的只是剪枝了暴力三重循环...思路就是创建左右指针左指针从 0 遍历至 串尾右指针则每次从 串尾 遍历至 左指针1。内部从两边向中间遍历窗口检查是否回文。然后各处剪枝一下即可。三、题解class Solution { public: string longestPalindrome(string s) { string res(1,s[0]); for(int i0;is.length();i){ int lefti; int rights.length()-1; while(leftright){ if((right-left)res.length()) break; //当左右指针间隔比目前找到的最大回文子串长度小则直接结束剪枝 bool foundtrue; //判断是否是回文 for(int j0;j(right-left)/2;j){ //依次对比每个字符 char ls[leftj]; char rs[right-j]; if(l!r){ //一旦不同就直接置否不是回文 foundfalse; break; //break剪枝 } } if(found){ //如果检查了一遍之后都没有置否就说明是回文 ress.substr(left,right-left1); break; } else right--; //不是回文则缩小窗口继续检查 } } return res; } };

更多文章