Title: Algorithm (leetode, with mind mapping + all solutions) 300 questions (5) the longest back text substring
A Description of the topic
Overview of Two Solutions (Mind Mapping)
Three complete solutions
Scheme 1
1) code:
// Solution 1: sliding window method (" high time complexity, generally cannot pass ")
var longestPalindrome = function(s) {
// Whether it is a palindrome string. (subStr = "for a little programming rigor")
const isValid = (subStr = ' ') = > {
const l = subStr.length;
let resFlag = true;
// Boundary: I < L /2
for(let i = 0; i < l/2; i++) {
// If the characters in "symmetric position" are not equal, then it must not be a palindrome
if(subStr[i] ! == subStr[(l -1) - i]) {
resFlag = false;
break; }}return resFlag;
}
const l = s.length;
// curMaxLength Specifies the maximum length of the current callback substring. The range is [l, 1].
for (let curMaxLength = l; curMaxLength > 0; curMaxLength--) {
// Under curMaxLength, the valid range of curStartIndex is [0, ((l + 1) - curMaxLength))
for (let curStartIndex = 0; curStartIndex < ((l + 1) - curMaxLength); curStartIndex++) {
const subStr = s.substr(curStartIndex, curMaxLength);
// Once the palindrome is matched, the current substring must be the expected answer (" one ").
// Because we curMaxLength is decreasing each time we iterate
if (isValid(subStr)) {
returnsubStr; }}}// <= s.length <= 1000; // <= 1;
return "";
}
Copy the codeScheme 2
1) code:
/ / the dynamic programming, plan 2 (s = = = s [j] [I] && dp + 1] [I] [j - 1) | | (s = = = s [j] [I] && (j + 1) - (I) < 3)
var longestPalindrome = function(s) {
const l = s.length,
S [I][j] indicates whether s[I, j] is a palindrome (double closed interval)
// Initialize 1: dp with n*n values initialized to false
dp = new Array(l).fill(false).map(item= > new Array(l).fill(false));
// The starting substring and the maximum length of the current longest substring
let maxStartIndex = 0.// Boundary: maxLength is initialized to 1. Otherwise there will be problems, can think by themselves ~
maxLength = 1;
// Initialize 2: dp is true on the diagonal
for (let i = 0; i < l; i++) {
for(let j = 0; j < l; j++) {
if (i === j) {
dp[i][j] = true; }}}// 2) State transition equation:
// s[i][j] = (s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3)
// s[I][j] = (1, 2, 3)
// or (The first and last characters are the same && The interval between the first and last characters is < 3.) If the length of "bb" is less than 3, ensure that the first and last characters are the same
for (let j = 1; j < l; j++) {
for(let i = 0; i < j; i++) {
if ((s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3)) {
dp[i][j] = true;
// If s[I, j] is a palindrome, we need to update maxStartIndex and maxLength
// 3) Update the maxStartIndex and maxLength values when s[I, j] is a palindrome && (j + 1) -i) > maxLength
if (((j + 1) - i) > maxLength) {
maxStartIndex = i;
maxLength = ((j + 1) - i); }}else {
dp[i][j] = false; }}}MaxStartIndex; maxLength
return s.substr(maxStartIndex, maxLength);
}
Copy the code3 solution 3
1) code:
// Plan 3: The central diffusion method (note "both odd and even cases")
var longestPalindrome = function(s) {
// Try to get a longer palindrome based on the substring passed in, left and right boundary subscripts
const helper = (str, left, right) = > {
while(left >=0 && right < l) {
if (str[left] === str[right]) {
// Check whether the maxStartIndex and maxLength values need to be updated
if ((right + 1 - left) > maxLength) {
maxStartIndex = left;
maxLength = (right + 1 - left);
}
// Note: these two statements are placed at the end of the current if branch, not at the beginning!
// Keep moving "outward" to try to get a longer palindrome string
left--;
right++;
} else {
// At this time STR [left]! == STR [right] == STR [right]
break; }}}const l = s.length;
// The starting index and maximum length of the current longest palindrome string.
let maxStartIndex = 0,
maxLength = 0;
for (let i = 0 ; i < l; i++) {
// 1) Odd: try to get a longer palindrome string by moving out with s[I]
helper(s, i ,i);
// 2) Even: try to get a longer palindrome string by moving out with s[I], s[I + 1]
helper(s, i, i + 1);
}
return s.substr(maxStartIndex, maxLength);
}
Copy the code4 scheme 4
1) code:
// Scheme 4 Manacher (" horse-drawn cart ") algorithm
class Solution {
public String longestPalindrome(String s) {
int start = 0, end = -1;
StringBuffer t = new StringBuffer("#");
for (int i = 0; i < s.length(); ++i) {
t.append(s.charAt(i));
t.append(The '#');
}
t.append(The '#');
s = t.toString();
List<Integer> arm_len = new ArrayList<Integer>();
int right = -1, j = -1;
for (int i = 0; i < s.length(); ++i) {
int cur_arm_len;
if (right >= i) {
int i_sym = j * 2 - i;
int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
} else {
cur_arm_len = expand(s, i, i);
}
arm_len.add(cur_arm_len);
if (i + cur_arm_len > right) {
j = i;
right = i + cur_arm_len;
}
if (cur_arm_len * 2 + 1 > end - start) {
start = i - cur_arm_len;
end = i + cur_arm_len;
}
}
StringBuffer ans = new StringBuffer();
for (int i = start; i <= end; ++i) {
if(s.charAt(i) ! =The '#') { ans.append(s.charAt(i)); }}return ans.toString();
}
public int expand(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return (right - left - 2) / 2; }}Copy the code