1 topic and related definition introduction

1.1 Introduction

Given a string s, find the longest substring in s.

Example 1: Input: s = "babad" Output: "bab" Explanation: "ABA" is also the answer to the question. Example 2: Input: s = "CBBD" Output: "bb" Hint: 1 <= S.length <= 1000 s Consists of only digits and English letters (uppercase and/or lowercase)Copy the code

Title source: leetcode-cn.com/problems/lo…

2.2 Related Definitions

substring

A subsequence of any consecutive characters in a string is called a substring of the string; And then there is the concept of subsequence, subsequence is to find a part of the original sequence;

The difference between

For a string: helloStoney; A substring is a string in which a block (consecutive) is taken, such as Hello, Stoney; Subsequence refers to the sequential extraction of characters from the string, but can be discontinuous, such as HLO, hlSn, etc

2. Violent solution

Method to introduce

  • List all substrings, time: O(n^2)
  • Check whether each substring is a textual substring, and the time complexity of each substring: O(n)
  • Total time complexity O(n^3), space complexity O(1);

Dynamic programming solution

3.1 Detailed explanation of solution

The dynamic programming solution is based on the optimization of the violence solution. The optimization part is to judge whether each string is a palindrome string; Time complexity: O(n^2); Space complexity: O(n^2); The space complexity can be optimized to O(n).

Suppose the string (“abbaba”) is s, which has length N; Define dp array, dp[I][j] : indicates whether s[I][j] is a subroutine, storage value is 0, 1; 1, if the length of s[I, j] (j – I + 1) <= 2, if the length of s[I, j] (j – I + 1) <= 2;

  • If s = = = s [j] [I], then s [I] [j] is a palindrome string, so dp [I] [j] [I] = = = = s s [j];

2, if the length of s[I, j] (j-i + 1) > 2;

  • If s[I + 1, j-1] is a palindrome string and s[I] === S [j], then S [I, j] is a palindrome string;
  • So dp[I][J] = DP [I + 1, J-1] &&s [I] === S [J];

3.2 Code Implementation

var longestPalindrome = function(s) {
    let length = s.length;
    if(s == null) return null;
    if(length <= 1) {
        return s;
    }
    let dp = Array.from(new Array(length), () => new Array(length).fill(0));
    let maxlen = 1;
    let begin = 0;
    for (let i = length - 1; i >= 0; i--) {
        for (let j = i; j < length; j++) {
            let len = j - i + 1;
            dp[i][j] = (s[i] === s[j]) && (len <= 2 || dp[i + 1][j - 1]);
            if(dp[i][j] && len > maxlen) {
                maxlen = len;
                begin = i;
            }
        }
    }
    return s.substring(begin, begin + maxlen)
};
Copy the code

Diffusion center solution

4.1 Solution introduction

If as shown: there are two modes of diffusion; Assuming that the string (“abbaba”) is of length N, there are n + (n-1) = 2n-1 extension centers; Time complexity: O(n^2) Space complexity: O(1);

4.2 Code Implementation

var longestPalindrome = function(s) { if (s === null) return null; let length = s.length; if(length <= 1) return s; let maxLen = 1; let begin = 0; for (let i = length - 2; i >= 1; I --) {// let len1 = palindromeLength(s, i-1, I + 1); // let len2 = palindromeLength(s, I, I + 1); len1 = Math.max(len1, len2); if(len1 > maxLen) { maxLen = len1; begin = i - ((maxLen - 1) >> 1); If (s[0] === s[1] && maxLen < 2) {begin = 0; maxLen = 2; } return s.substring(begin, maxLen + begin) }; // From l to the left, from r to the right, Function palindromeLength(s, l, r) {while(l >= 0 &&r < s.length &&s [l] === s[r]) {l--; r++; } return r - l - 1; }Copy the code

Optimization of diffusion center solution

5.1 Introduction to the solution

The core idea of the algorithm is as follows: the substring composed of the same continuous characters as the diffusion center; So, “babbbabaa” the spread of the center are: “b”, “a”, “BBB”, “a”, “b”, “aa”.

Find the first character on the left that is not equal to s[I], denoted by position r, denoted by position L on the left of I; R is I for the next time; Starting from l to the left and r to the right, find the longest subroutine;

5.2 Code Implementation

var longestPalindrome = function(s) { if (s === null) return null; let length = s.length; if(length <= 1) return s; let maxLen = 1; let begin = 0; let i = 0; while(i < length) { let l = i - 1; Let r = I; // let r = I; while(++r < length && s[r] === s[i]); // r will become the new I I = r; / / from the left, l r spread to the right while && (l > = 0 r < length && s [l] = = = s [r]) {l -; r++; Len = r - ++l; if(len > maxLen) {maxLen = len; if(len > maxLen) {maxLen = len;  begin = l; } } return s.substring(begin, begin + maxLen) };Copy the code