This is the 38th day of my participation in the First Challenge 2022.

Longest palindromic substring

LeetCode portal 5. The longest loop substring

The title

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

Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad" Output: "bab" Explanation: "ABA" is also the answer to the question. Input: s = "CBBD" Output: "bb"Copy the code

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Thinking line

Their thinking

Solve the problem according to the palindrome center

Since every anaphora has a palindrome center, this palindrome center is either one character or two characters.

We can loop s and treat s[I] or S [I],s[I +1] as a palindrome center. We can easily get the following code.

function longestPalindrome(s: string) :string {
    let longest = ' ';
    const len = s.length
    for (let i = 0; i < len; i++) {
        // Palindrome center is I, or I, I +1

        let j = i
        let item = s[i]
        let m = 1;
        while (j - m >= 0 && j + m < len) {
            const b = s[j - m]
            const a = s[j + m]
            if (b === a) {

                item = b + item + a;
                m++
            } else {
                break; }}if (longest.length < item.length) longest = item;

        // is I, I + 1;
        if (s[i] === s[i + 1] && i + 1 < len) {
            let j = i
            let item = s[i] + s[i + 1];
            let m = 1;
            while (j - m >= 0 && j + m + 1 < len) {
                const b = s[j - m]
                const a = s[j + m + 1]
                if (b === a) {

                    item = b + item + a;
                    m++
                } else {
                    break; }}if(longest.length < item.length) longest = item; }}return longest;

};
Copy the code

At this point, I have no idea how to get a better solution. So I went to look at the answers written by other friends. This is the same idea, but there is a friend who encapsulates the code better than ME.

function longestPalindrome(s: string) :string {
    if(s.length < 2) {return s
    }
    let start:number = 0
    let maxLength:number = 1
    function fn(left:number,right:number){
        while(left >= 0 && right < s.length && s[left] === s[right]){
            if(right - left + 1 > maxLength){
                maxLength = right -left + 1
                start = left
            }
            left--
            right++
        }
    }
    for(let i:number = 0; i<s.length; i++){ fn(i -1,i + 1)
        fn(i,i + 1)}return s.substring(start,start + maxLength)
};
Copy the code

Time complexity

O(n2)O(n^2)O(n2): n is a character string. There are n and n-1 palindromic centers of length 1 and 2 respectively, and each palindromic center extends outwardly at most O(n) times.

Problem solving with dynamic programming

Moving problem, really is a look will be useless, a write, or failed to write out. Read the solution, write down the experience, I hope to do it next time.

There are a couple of things to think about in terms of dynamic programming

1. Find states and Choices

2. Define dp arrays/functions

3. Look for relationships between “states.

4. What is our state in this problem? We’re looking for the smallest and longest substring, and in the substring, there are two states where the substring is true and the substring is not false.

5. Define dp arrays/functions. It is clear that a string requires at least two indexLeft, right, so we define dp as a two-dimensional array, P[left, right], where left and right are the beginning and end points of the substring.

6. Finding relationships between “states” Suppose a substring is s[left, right] (left < right)

   • If it is not itself a subroutine, it cannot form a longer subroutine.
   • If it is itself a subroutine, then if it satisfiess[left -1] ===s[right+1]thes[left-1, right +1]It’s also a palindrome string.

   Then we can get the state transition equation for dynamic programming

   
   $P(i, j) = P(i+1, j -1) \&\& s[i] === s[j]$

   The transfer equation above is the substring length greater than 2. We also need to consider the boundary condition in dynamic programming, that is, the substring length is 1 or 2.

   • If the substring is of length 1 it’s obviously a palindrome string
   • If the length is 2, it is also a palindrome string as long as the letters are the same

   Thus, we can write the boundary conditions of dynamic programming:

   
   $${}\begin{cases} P(i,i) = true\\ P(i, i+1) = s[i] === s[i+1] \end{cases}$$

With the above ideas, we can complete dynamic programming. The final answer is the maximum value of j-i+1(the substring length) for all P(I,j) = true.

Based on the above ideas, I wrote the following code:

function longestPalindrome(s: string) :string {
    const len = s.length;
    let maxLen = 1;
    let start = 0;

    const dp: boolean[] [] =Array.from(new Array(len), () = > new Array(len).fill(false));

    // All strings of length 1 are palindromes
    for (let i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    for (let L = 2; L <= len; L++) {
        for (let i = 0; i < len; i++) {
            J - I + 1 = L
            const j = L + i - 1;
            // If the right boundary is out of bounds, we can exit the current loop
            if (j >= len) {
                break;
            }

            if(s[i] ! = s[j]) { dp[i][j] =false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1]; }}// if dp[I][L] == true, then s[I..L] is a palindrome
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1; start = i; }}}return s.substring(start, start + maxLen);

};
Copy the code

Time complexity

O(n2)O(n^2)O(n2): Indicates that the total number of states in dynamic programming is N2N ^2n2.

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.