資訊專欄INFORMATION COLUMN
摘要：以下是最長回文子串的相關(guān)代碼，相關(guān)邏輯已在注釋中注明我們?cè)械淖址赡艽嬖趦煞N回文子串，一種是具有基數(shù)個(gè)元素例如一種是具有偶數(shù)個(gè)元素例如這樣的話分情況判斷比較復(fù)雜所以我們對(duì)原字符串進(jìn)行擴(kuò)充在相鄰元素中插入特殊值插入后的原基數(shù)回文子串變成了
以下是最長回文子串的Manacher‘s Algorithm相關(guān)代碼，相關(guān)邏輯已在注釋中注明：
public static String solution(String s) {
if (s.length() == 0) {
return "";
}
//我們?cè)械淖址赡艽嬖趦煞N回文子串，一種是具有基數(shù)個(gè)元素例如aba 一種是具有偶數(shù)個(gè)元素例如abba 這樣的話分情況判斷比較復(fù)雜
//所以我們對(duì)原字符串進(jìn)行擴(kuò)充 在相鄰元素中插入特殊值 插入后的原基數(shù)回文子串變成了#a#b#a# 原偶數(shù)回文子串變成了#a#b#b#a# 都變成了基數(shù)回文子串 便于后續(xù)的運(yùn)算
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] = "#";
//初始化標(biāo)識(shí)數(shù)組，此數(shù)組用來表示chars中某個(gè)元素的回文子串半徑值
int[] l = new int[chars.length];
l[0] = 1;
//其中max為已探明的回文子串中能擴(kuò)展到最右的邊界位置 id為前述回文子串的中心位置 resid為最終解的中心值
int max = 1, id = 0, resid = 0;
//循環(huán)獲取最長回文子串
for (int i = 1; i < l.length; i++) {
// 當(dāng)max>i時(shí)當(dāng)前數(shù)組為如下結(jié)構(gòu)：
// beg-------min----j-----id-----i----max-----end
//其中beg和end分別為數(shù)組的邊界位置 j=2*id-i 是i對(duì)于id的對(duì)稱值 （當(dāng)max>i時(shí)此對(duì)稱值肯定會(huì)有并且肯定大于min，當(dāng)max i ? Math.min(l[2 * id - i], max - i) : 1;
//對(duì)獲取的半徑進(jìn)行迭代擴(kuò)充回文序列的長度
while (i - l[i] >= 0 && i + l[i] <= chars.length - 1 && chars[i - l[i]] == chars[i + l[i]]) {
l[i]++;
}
//如果當(dāng)前的回文序列最右邊界位置已經(jīng)大于了max 則更新max和id為當(dāng)前回文序列的相關(guān)值
if (i + l[i] - 1 > max) {
max = i + l[i] - 1;
id = i;
}
//如果當(dāng)前的回文序列長度為最長，則更新resid的值
if (l[i] > l[resid]) {
resid = i;
//如果當(dāng)前的回文序列長度和之前記錄的最長回文序列的長度相同則存在如下情況：
// 1、之前最長回文序列長度為1 但是此時(shí)中心為擴(kuò)充值 比如a#b中 #為中心 長度為1 這樣的序列并不能當(dāng)作解來使用，如果發(fā)現(xiàn)了以原字符串中字符為中心的長度相同的串則要更新這個(gè)值
// 2、之前最長回文序列中心值為擴(kuò)充值，例如#a#a#長度為5對(duì)應(yīng)原字符串中子串為aa，但是存在以原字符串的值為中心的序列比如a#b#a 長度為5，此時(shí)對(duì)應(yīng)的原字符串為aba 可見長度相同但是最后的結(jié)果有差別
// 所以此處進(jìn)行判斷來避免如上兩種問題
} else if (l[i] == l[resid] && resid % 2 == 0) {
resid = i;
}
}
StringBuilder sb = new StringBuilder();
int resBeg = resid - l[resid] + 1;
//根據(jù)得到的resid和其半徑 獲取最后的結(jié)果
while (resBeg <= resid + l[resid] - 1) {
if (resBeg % 2 == 1) {
sb.append(chars[resBeg]);
}
resBeg++;
}
return sb.toString();
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77845.html
摘要：問題定義最長回文子串問題給定一個(gè)字符串，求它的最長回文子串長度?？梢圆捎脛?dòng)態(tài)規(guī)劃，列舉回文串的起點(diǎn)或者終點(diǎn)來解最長回文串問題，無需討論串長度的奇偶性。 0. 問題定義 最長回文子串問題：給定一個(gè)字符串，求它的最長回文子串長度。 如果一個(gè)字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實(shí)例： 12321 a aba abba aaaa tatt...
摘要：難度題目是說給出一個(gè)字符串求出這個(gè)字符串的最長回文的子串回文是指前后完全對(duì)稱的字符串像是之類的都算是回文奇數(shù)字母的回文和偶數(shù)字母的回文中心是不一樣的奇數(shù)字母比如的中心在中間字母上偶數(shù)字母比如的回文在中間兩字母的中心上由此可見回文中心點(diǎn)實(shí)際上 Given a string s, find the longest palindromic substring in s. You may as...
摘要：一題目最長回文子串給定一個(gè)字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個(gè)有效答案。 一、題目 最長回文子串： 給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。 示例 1： 輸入: babad輸出: bab注意: aba 也是一個(gè)有效答案。 示例 2： 輸入: cbbd輸出: bb 二、我的答案 思路 1.排...
摘要：最長回文子串給定一個(gè)字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個(gè)有效答案。 LeetCode5.最長回文子串 JavaScript 給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。示例 1： 輸入: babad 輸出: bab 注意: aba 也是一個(gè)有效答案。 示例 2： 輸入: cbbd輸出: bb /*...
閱讀 2824·2023-04-25 22:51
閱讀 2084·2021-10-11 10:58
閱讀 3323·2019-08-30 10:49
閱讀 1889·2019-08-29 17:09
閱讀 3147·2019-08-29 10:55
閱讀 854·2019-08-26 10:34
閱讀 3513·2019-08-23 17:54
閱讀 996·2019-08-23 16:06
