Java实现 LeetCode 5 最长回文子串
2023-09-14 08:58:07 时间
5. 最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
// 保存起始位置,测试了用数组似乎能比全局变量稍快一点
int[] range = new int[2];
char[] str = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
// 把回文看成中间的部分全是同一字符,左右部分相对称
// 找到下一个与当前字符不同的字符
i = findLongest(str, i, range);
}
return s.substring(range[0], range[1] + 1);
}
public static int findLongest(char[] str, int low, int[] range) {
// 查找中间部分 防止abbba
int high = low;
while (high < str.length - 1 && str[high + 1] == str[low]) {
high++;
}
// 定位中间部分的最后一个字符
int ans = high;
// 从中间向左右扩散
while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
low--;
high++;
}
// 记录最大长度
if (high - low > range[1] - range[0]) {
range[0] = low;
range[1] = high;
}
return ans;
}
}
相关文章
- Java实现 LeetCode 835 图像重叠(暴力)
- Java实现 LeetCode 824 山羊拉丁文(暴力)
- Java实现 LeetCode 814 二叉树剪枝 (遍历树)
- Java实现 LeetCode 802 找到最终的安全状态 (DFS)
- Java实现 LeetCode 770 基本计算器 IV(暴力+分析题)
- Java实现 LeetCode 753 破解保险箱(递归)
- Java实现 LeetCode 731 我的日程安排表 II(二叉树)
- Java实现 LeetCode 724 寻找数组的中心索引(暴力)
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- Java实现 LeetCode 504 七进制数
- Java实现 LeetCode 446 等差数列划分 II - 子序列
- Java实现 LeetCode 414 第三大的数
- Java实现 LeetCode 396 旋转函数
- Java实现 LeetCode 328 奇偶链表
- Java实现 LeetCode 322 零钱兑换
- Java实现 LeetCode 129 求根到叶子节点数字之和
- Java实现 LeetCode 117 填充每个节点的下一个右侧节点指针 II(二)
- Java实现 LeetCode 83 删除排序链表中的重复元素
- Java实现 LeetCode 82 删除排序链表中的重复元素 II(二)
- Java实现 LeetCode 47 全排列 II(二)
- Java实现 LeetCode 41 缺失的第一个正数
- Java实现 LeetCode 20 有效的括号
- Java实现 LeetCode 11 盛最多水的容器
- Java实现 LeetCode 9 回文数
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- Java实现 Leetcode 169 求众数
- 【LeetCode-面试算法经典-Java实现】【130-Surrounded Regions(围绕区域)】
- JAVA语言之Java 中不同的并行实现的性能比较