摘要:以下是最長回文子串的相關代碼,相關邏輯已在注釋中注明我們原有的字符串可能存在兩種回文子串,一種是具有基數個元素例如一種是具有偶數個元素例如這樣的話分情況判斷比較復雜所以我們對原字符串進行擴充在相鄰元素中插入特殊值插入后的原基數回文子串變成了
以下是最長回文子串的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();
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/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 /*...
閱讀 2814·2023-04-25 22:51
閱讀 2048·2021-10-11 10:58
閱讀 3313·2019-08-30 10:49
閱讀 1876·2019-08-29 17:09
閱讀 3139·2019-08-29 10:55
閱讀 845·2019-08-26 10:34
閱讀 3488·2019-08-23 17:54
閱讀 983·2019-08-23 16:06