摘要：以下是最长回文子串的相关代码，相关逻辑已在注释中注明我们原有的字符串可能存在两种回文子串，一种是具有基数个元素例如一种是具有偶数个元素例如这样的话分情况判断比较复杂所以我们对原字符串进行扩充在相邻元素中插入特殊值插入后的原基数回文子串变成了
以下是最长回文子串的Manacher‘s Algorithm相关代码，相关逻辑已在注释中注明：
public static String solution(String s) {
if (s.length() == 0) {
return "";
}
//我们原有的字符串可能存在两种回文子串，一种是具有基数个元素例如aba 一种是具有偶数个元素例如abba 这样的话分情况判断比较复杂
//所以我们对原字符串进行扩充 在相邻元素中插入特殊值 插入后的原基数回文子串变成了#a#b#a# 原偶数回文子串变成了#a#b#b#a# 都变成了基数回文子串 便于后续的运算
char[] chars = new char[s.length() * 2 + 1];
for (int i = 0; i < s.length(); i++) {
chars[2 * i] = "#";
chars[2 * i + 1] = s.charAt(i);
}
chars[chars.length - 1] = "#";
//初始化标识数组，此数组用来表示chars中某个元素的回文子串半径值
int[] l = new int[chars.length];
l[0] = 1;
//其中max为已探明的回文子串中能扩展到最右的边界位置 id为前述回文子串的中心位置 resid为最终解的中心值
int max = 1, id = 0, resid = 0;
//循环获取最长回文子串
for (int i = 1; i < l.length; i++) {
// 当max>i时当前数组为如下结构：
// beg-------min----j-----id-----i----max-----end
//其中beg和end分别为数组的边界位置 j=2*id-i 是i对于id的对称值 （当max>i时此对称值肯定会有并且肯定大于min，当max i ? Math.min(l[2 * id - i], max - i) : 1;
//对获取的半径进行迭代扩充回文序列的长度
while (i - l[i] >= 0 && i + l[i] <= chars.length - 1 && chars[i - l[i]] == chars[i + l[i]]) {
l[i]++;
}
//如果当前的回文序列最右边界位置已经大于了max 则更新max和id为当前回文序列的相关值
if (i + l[i] - 1 > max) {
max = i + l[i] - 1;
id = i;
}
//如果当前的回文序列长度为最长，则更新resid的值
if (l[i] > l[resid]) {
resid = i;
//如果当前的回文序列长度和之前记录的最长回文序列的长度相同则存在如下情况：
// 1、之前最长回文序列长度为1 但是此时中心为扩充值 比如a#b中 #为中心 长度为1 这样的序列并不能当作解来使用，如果发现了以原字符串中字符为中心的长度相同的串则要更新这个值
// 2、之前最长回文序列中心值为扩充值，例如#a#a#长度为5对应原字符串中子串为aa，但是存在以原字符串的值为中心的序列比如a#b#a 长度为5，此时对应的原字符串为aba 可见长度相同但是最后的结果有差别
// 所以此处进行判断来避免如上两种问题
} else if (l[i] == l[resid] && resid % 2 == 0) {
resid = i;
}
}
StringBuilder sb = new StringBuilder();
int resBeg = resid - l[resid] + 1;
//根据得到的resid和其半径 获取最后的结果
while (resBeg <= resid + l[resid] - 1) {
if (resBeg % 2 == 1) {
sb.append(chars[resBeg]);
}
resBeg++;
}
return sb.toString();
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/77845.html
摘要：问题定义最长回文子串问题给定一个字符串，求它的最长回文子串长度。可以采用动态规划，列举回文串的起点或者终点来解最长回文串问题，无需讨论串长度的奇偶性。 0. 问题定义 最长回文子串问题：给定一个字符串，求它的最长回文子串长度。 如果一个字符串正着读和反着读是一样的，那它就是回文串。下面是一些回文串的实例： 12321 a aba abba aaaa tatt...
摘要：难度题目是说给出一个字符串求出这个字符串的最长回文的子串回文是指前后完全对称的字符串像是之类的都算是回文奇数字母的回文和偶数字母的回文中心是不一样的奇数字母比如的中心在中间字母上偶数字母比如的回文在中间两字母的中心上由此可见回文中心点实际上 Given a string s, find the longest palindromic substring in s. You may as...
摘要：一题目最长回文子串给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。 一、题目 最长回文子串： 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: babad输出: bab注意: aba 也是一个有效答案。 示例 2： 输入: cbbd输出: bb 二、我的答案 思路 1.排...
摘要：最长回文子串给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。 LeetCode5.最长回文子串 JavaScript 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1： 输入: babad 输出: bab 注意: aba 也是一个有效答案。 示例 2： 输入: cbbd输出: bb /*...
阅读 2765·2023-04-25 22:51
阅读 1972·2021-10-11 10:58
阅读 3287·2019-08-30 10:49
阅读 1803·2019-08-29 17:09
阅读 3115·2019-08-29 10:55
阅读 806·2019-08-26 10:34
阅读 3419·2019-08-23 17:54
阅读 963·2019-08-23 16:06
