5. The longest subroutine string
- Author: Chen Da Yu Tou
- Making: KRISACHAN
- This repository is used to record fish head LeetCode solutions, mainly implemented in Python3, JavaScript and TypeScript.
Title description:
Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000.
Example 1:
// Enter: "babad"
// output: "bab"
// Note: "ABA" is also a valid answer.
Copy the codeExample 2:
// Enter: "CBBD"
// output: "bb"
Copy the codeTheir thinking
Solution 1 – Center extension method
Because of the symmetry of palindrome strings, one number can be selected as the center at a time, and left and right expansion can be carried out to determine whether it is a palindrome string. Since the string can be odd, it can be even, so you need to expand from 1 to 2 characters. That means I + I – 1 extension centers. Then I is an odd digit, and I + 1 is an even digit. And that’s the basis of the theory that every time you go through the cycle you just expand on both sides. The solution is O(n^2). The space complexity is order 1.
Solution 2 – Horse-drawn cart algorithm
I’m new to this algorithm, but the guy who came up with it, he’s awesome. The horse-drawn cart algorithm increases the time complexity to linear. The algorithm starts by iterating through the characters, inserting a special symbol on both sides of each character, and adding a special label at the beginning and end of each character, for example, aabbcbbaa -> ^#a#a#b#b#c#b# a#a# a#$to ensure that the current string must be odd. And then expand left and right. Use an array arr with the length of the original string to hold the maximum number of center extensions. (arr the subscript of each element -arr [I]) / 2 is the subscript of the original string character. Let C be the center of the string and R be the length to the right of the string, so R = C + arr[I]. And then you can use the center extension method. We use j to denote the subscript of the ith character corresponding to C. However, there are the following three situations that lead to incorrect ARR [J]
-
The length goes beyond R
-
Arr [j] reaches the left boundary of the original string
-
When I is just R
Therefore, in the above three cases, we need to use the center extension method to do boundary processing.
JS version
/** * @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 = A '^'
for (let i = 0, len = s.length; i < len; ++i) {
res = res + The '#' + 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 // The center of the subroutine with the largest right margin
let R = 0 // substring right boundary
for (let i = 1; i < len - 1; ++i) {
let j = 2 * C - i
if (R > i) {
arr[i] = Math.min(R - i, arr[j]) // right edge processing
} else {
arr[i] = 0
}
// For the above three special cases, use the center extension method
while (str[i + 1 + arr[i]] === str[i - 1 - arr[i]]) {
arr[i]++
}
// Determine whether R needs to be updated
if (i + arr[i] + R) {
C = i
R = i + arr[i]
}
}
let maxLen = 0 // Maximum length
let index = 0 // Center subscript
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)
}
Copy the codeTS edition
Because of the symmetry of the palindrome string, you can choose a number as the center each time, and expand left and right to determine whether it is a palindrome string. * Since the string can be odd or even, you need to expand from 1 to 2 characters. * Means there are I + I - 1 extension centers. * And the I digit * I + 1 is an even digit *. * * The time complexity is 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 = A '^'
for (let i: number = 0, len = s.length; i < len; ++i) {
res = res + The '#' + 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 // The center of the subroutine with the largest right margin
let R: number = 0 // substring right boundary
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]) // right edge processing
} else {
arr[i] = 0
}
// For the above three special cases, use the center extension method
while (str[i + 1 + arr[i]] == str[i - 1 - arr[i]]) {
arr[i]++
}
// Determine whether R needs to be updated
if (i + arr[i] + R) {
C = i
R = i + arr[i]
}
}
let maxLen: number = 0 // Maximum length
let index: number = 0 // Center subscript
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)
}
Copy the codePY version
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 = A '^'
for i in range(len(s)):
res += The '#'
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]
Copy the codeIf you like to discuss technology, or have any comments or suggestions on this article, you are welcome to add yu Tou wechat friends to discuss. Of course, Yu Tou also hopes to talk about life, hobbies and things with you. You can also scan your wechat account to subscribe to more exciting content.
