本次題目描述：
創(chuàng)新互聯(lián)公司主營(yíng)巴州網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,app軟件開發(fā),巴州h5微信小程序定制開發(fā)搭建,巴州網(wǎng)站營(yíng)銷推廣歡迎巴州等地區(qū)企業(yè)咨詢
給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。
示例 1:
重慶分公司
重慶分公司
// 輸入:
"babad"
// 輸出:
"bab"
// 注意:
"aba" 也是一個(gè)有效答案。
示例 2:
// 輸入:
"cbbd"
// 輸出:
"bb"
解題思路
解法1 - 中心拓展法
由于回文字符串的對(duì)稱性，所以每次可以選擇一個(gè)數(shù)字作為中心，進(jìn)行左右拓展來判斷是否是回文串。
由于字符串有可能為奇數(shù)，有可能為偶數(shù)，所以需要從 1 or 2個(gè)字符之間開始拓展。
意思就是有 i + i - 1個(gè)拓展中心。
則 i 為奇數(shù)位，
i + 1為偶數(shù)位。
以此為理論依據(jù)每次循環(huán)往兩邊拓展即可。
此解法時(shí)間復(fù)雜度是O(n^2)。
空間復(fù)雜度是O(1)。
解法2 - 馬拉車算法
第一次接觸這個(gè)算法，但是想出這個(gè)算法的人，確實(shí)牛逼。
馬拉車算法將時(shí)間復(fù)雜度提升到了線性。
此算法最初遍歷字符，在每個(gè)字符兩邊都插入一個(gè)特殊符號(hào)，為避免越界，首尾加上特殊標(biāo)簽，例如：
aabbcbbaa -> ^#a#a#b#b#c#b#b#a#a#$
保證當(dāng)前字符串一定為奇數(shù)。
然后左右擴(kuò)展。
利用一個(gè)長(zhǎng)度為原字符串長(zhǎng)度的數(shù)組arr來保存中心擴(kuò)展的最大個(gè)數(shù)。
(arr每個(gè)元素的下標(biāo) - arr[i]) / 2 就是原字符串的字符的下標(biāo)。
我們?cè)O(shè)C為字符串中心，R為字符串右邊的長(zhǎng)度，則有R = C + arr[i]。
這時(shí)候就可以用中心擴(kuò)展法去求。
我們用j表示第i個(gè)字符與C對(duì)應(yīng)的下標(biāo)。
但有以下三種情況會(huì)導(dǎo)致arr[j]不正確
所以遇到以上三種情況，我們需要利用中心拓展法去做邊界處理。
JS版
/**
*
@param
{string} str
*
@param
{number} left
*
@param
{number} right
*
@return
{number}
*/
const expandCenter =
(
str, left, right) => {
while (left >=
0 && right < str.length && str[left] === str[right]) {
left--
right++
}
return str.slice(left +
1, right)
}
/**
*
@param
{string} s
*
@return
{string}
*/
const longestPalindrome1 =
(
s) => {
if (!s || !s.length) {
return
''
}
let result =
''
for (
let i =
0; i < s.length; i++) {
const odd = expandCenter(s, i, i)
const even = expandCenter(s, i, i +
1)
if (odd.length > result.length) {
result = odd
}
if (even.length > result.length) {
result = even
}
}
return result
}
/**
*
@param
{string} s
*
@return
{string}
*/
const setTarget =
(
s) => {
if (!s) {
return
''
}
if (s.length ===
0) {
return
'^$'
}
let res =
'^'
for (
let i =
0, len = s.length; i < len; ++i) {
res = res +
'#' + s.charAt(i)
}
res +=
'#$'
return res
}
/**
*
@param
{string} s
*
@return
{string}
*/
const longestPalindrome2 =
(
s) => {
let str = setTarget(s)
let len = str.length
let arr =
new
Array(len)
let C =
0
// 右邊界最大的回文子串的中心
let R = 0 // 子串右邊界
for (let i = 1; i < len - 1; ++i) {
let j = 2 * C - i
if (R > i) {
arr[i] = Math.min(R - i, arr[j]) // 右邊界處理
} else {
arr[i] = 0
}
// 遇到上述三種特殊情況時(shí)，使用中心拓展法
while (str[i + 1 + arr[i]] === str[i - 1 - arr[i]]) {
arr[i]++
}
// 判斷是否需要更新R的值
if (i + arr[i] + R) {
C = i
R = i + arr[i]
}
}
let maxLen = 0 // 最大長(zhǎng)度
let index = 0 // 中心下標(biāo)
for (let i = 1; i < len - 1; ++i) {
if (arr[i] > maxLen) {
maxLen = arr[i]
index = i
}
}
let start = (index - maxLen) / 2
return s.substring(start, start + maxLen)
}
TS版
/**
* @解法1
* @思路
* 由于回文字符串的對(duì)稱性，所以每次可以選擇一個(gè)數(shù)字作為中心，進(jìn)行左右拓展來判斷是否是回文串。
* 由于字符串有可能為奇數(shù)，有可能為偶數(shù)，所以需要從 1 or 2個(gè)字符之間開始拓展。
* 意思就是有 i + i - 1個(gè)拓展中心。
* 而且 i 為奇數(shù)位
* i + 1為偶數(shù)位
* 以此為理論依據(jù)每次循環(huán)往兩邊拓展即可。
*
* 此方式時(shí)間復(fù)雜度是O(n^2)
*/
/**
* @param {string} str
* @param {number} left
* @param {number} right
* @return {number}
*/
const expandCenter = (str:
string, left:
number, right:
number):
string => {
while (left >=
0 && right < str.length && str[left] === str[right]) {
left--
right++
}
return str.slice(left +
1, right)
}
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome1 = (s:
string):
string => {
if (!s || !s.length) {
return
''
}
let result:
string =
''
for (
let i:
number =
0; i < s.length; i++) {
const odd:
string = expandCenter(s, i, i)
const even:
string = expandCenter(s, i, i +
1)
if (odd.length > result.length) {
result = odd
}
if (even.length > result.length) {
result = even
}
}
return result
}
const setTarget = (s:
string):
string => {
if (!s) {
return
''
}
if (s.length ===
0) {
return
'^$'
}
let res:
string =
'^'
for (
let i:
number =
0, len = s.length; i < len; ++i) {
res = res +
'#' + s.charAt(i)
}
res +=
'#$'
return res
}
const longestPalindrome2 = (s:
string):
string => {
let str:
string = setTarget(s)
let len:
number = str.length
let arr:
number[] =
new
Array(len)
let C:
number =
0
// 右邊界最大的回文子串的中心
let R: number = 0 // 子串右邊界
for (let i: number = 1; i < len - 1; ++i) {
let j: number = 2 * C - i
if (R > i) {
arr[i] = Math.min(R - i, arr[j]) // 右邊界處理
} else {
arr[i] = 0
}
// 遇到上述三種特殊情況時(shí)，使用中心拓展法
while (str[i + 1 + arr[i]] == str[i - 1 - arr[i]]) {
arr[i]++
}
// 判斷是否需要更新R的值
if (i + arr[i] + R) {
C = i
R = i + arr[i]
}
}
let maxLen: number = 0 // 最大長(zhǎng)度
let index: number = 0 // 中心下標(biāo)
for (let i: number = 1; i < len - 1; ++i) {
if (arr[i] > maxLen) {
maxLen = arr[i]
index = i
}
}
let start: number = (index - maxLen) / 2
return s.substring(start, start + maxLen)
}
PY版
from typing
import List
import math
def expandCenter(s: str, left:
int, right:
int) -> str:
while left >=
0 and right <
len(s) and s[left] == s[right]:
left -=
1
right +=
1
return s[left +
1: right]
def longestPalindrome1(s: str) -> str:
if not(s) or not(
len(s)):
return
''
result: str =
''
for i in
range(
len(s)):
odd: str = expandCenter(s, i, i)
even: str = expandCenter(s, i, i +
1)
if
len(odd) >
len(result):
result = odd
if
len(even) >
len(result):
result = even
return result
def setTarget(s: str) -> str:
if not(s):
return
''
if (
len(s) ==
0):
return
'^$'
res: str =
'^'
for i in
range(
len(s)):
res +=
'#'
res += s[i]
res +=
'#$'
return res
def longestPalindrome2(s: str) -> str:
newStr: str = setTarget(s)
l:
int =
len(newStr)
arr = [
0
for _ in
range(l)]
C:
int =
0
R:
int =
0
for i in
range(l -
1):
j:
int =
2 * C - i
if R > i:
arr[i] = min(R - i, arr[j])
else:
arr[i] =
0
while newStr[i +
1 + arr[i]] == newStr[i -
1 - arr[i]]:
arr[i] +=
1
if i + arr[i] + R:
C = i
R = i + arr[i]
maxLen:
int =
0
idx:
int =
0
for i in
range(
1, l -
1):
if arr[i] > maxLen:
maxLen =
int(arr[i])
idx = i
start:
int =
int((idx - maxLen) /
2)
return s[start:start + maxLen]大家有不同思路可以留言！
