Leetcode 50 day question brushing plan (day 4 - longest palindrome substring 14.00-16:20)

Tips ： When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right

---

Preface

Today, it's still a string 、、

One 、 Title Description

subject

Give you a string s, find s The longest palindrome substring in .

Example

Example 1：

Input ：s = “babad”
Output ：“bab”
explain ：“aba” It's the same answer .
Example 2：

Input ：s = “cbbd”
Output ：“bb”

Tips ：

1 <= s.length <= 1000
s It consists only of numbers and English letters

Two 、 Ideas

① At the beginning, the first try broke ( The code is below ）, Complexity O（n^2）, After that 161/180, Then consider optimizing
（ it is to be noted that , The size is 1 The string of must be palindrome string , If this question is not palindrome string, return the first character ）

② Because when there is a palindrome string , Just consider testing strings that are longer than existing strings , So every time I look j From the i The next place that is longer than the current palindrome string length starts to traverse backwards , That is, for two for The traversal range of the loop is further reduced ：

 for i in range(n-1):
            # The tested string must be better than the existing max_len Longer 
            for j in range(i+max(2,max_len+1),n+1):

At this point you can AC

③ Reuse C++ Write again ,c++ The way to judge whether a string is palindrome is ：

string rev=s;//rev Deposit s Reverse results 
std::reverse(rev.begin(),rev.end());

A simple inversion code ：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    
    string N;
    cin>>N;
    reverse(N.begin(), N.end());
    cout<<N<<endl;
}

Get string length ：s.length()

String slicing function ：substr function
Prototype ：string substr ( size_t pos = 0, size_t len = npos ) const;
function ： Get the substring .
Parameter description ：pos Is the starting position （ The default is 0）,len Is the length of a string （ The default is npos）
Return value ： Substring

but c++ Burst is obviously not enough , It's just past 55 A test point ：

therefore c Language must be used dp Or the method of center diffusion ：
The initial state ：

dp[i][i]=1; // A single character is a palindrome string 
dp[i][i+1]=1 if s[i]=s[i+1]; // Two consecutive identical characters are palindromes 

See https://leetcode.cn/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/ （ A figure ）
and https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-c-by-gpe3dbjds1/（C++ Code ）

3、 ... and 、 Code

1. Timeout code （python）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # String length 
        n=len(s)
        # Record the longest length and longest substring 
        max_len=0
        cur_len=0
        max_s=['']

        # Front pointer and back pointer 
        #front=0
        #rear=0
        # In order to slice well , Add a character at the end of the string 
        s+='0'

        # Burst , Every time I look for j From the i Start traversing backwards where two character substrings can be formed later 
        for i in range(n-1):
            for j in range(i+2,n+1):
                temp=s[i:j]
                if(temp==temp[::-1]):
                    cur_len=len(temp)
                    if(cur_len>max_len):
                        max_len=cur_len
                        max_s[0]=temp
       
        # The largest palindrome string of a single character is itself , If there is no , Return initial 
        if(max_s[0]):
            return max_s[0]
        else:
            return s[0]

2.AC Code （python edition ）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # String length 
        n=len(s)
        # Record the longest length and longest substring 
        max_len=0
        cur_len=0
        max_s=['']

        # Go through the string first 

        # Front pointer and back pointer 
        #front=0
        #rear=0
        # In order to slice well , Add a character at the end of the string 
        s+='0'


        # Burst 
        for i in range(n-1):
            # The tested string must be longer than the existing one 
            for j in range(i+max(2,max_len+1),n+1):
                temp=s[i:j]
                if(temp==temp[::-1]):
                    cur_len=len(temp)
                    if(cur_len>max_len):
                        max_len=cur_len
                        max_s[0]=temp
                #print(i,j,max_s[0])
       
        # The largest palindrome string of a single character is itself , If there is no , Return initial 
        if(max_s[0]):
            return max_s[0]
        else:
            return s[0]

3. Timeout burst code （c++ edition ）

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        // Get the necessary data first : String length 、
        int n = s.length();
        string max_s="";
        int max_len=0;

        // String plus a character 
        s+='0';

        // Traverse 
        for(int i=0;i<n-1;i++){
    
            // here j Is the length of the string 
            for(int j=max(2,max_len+1); j<n+1-i; j++){
    
                string temp=s.substr(i,j);
                //cout<<temp<<" ";
                string rev=temp;
                reverse(rev.begin(),rev.end());
                //cout<<rev<<" ";
                if(temp==rev){
    
                    max_len=temp.length();
                    max_s=temp;
                }
                //cout<<i<<" "<<j<<" "<<max_s<<" "<<max_len<<endl;
            }
        }
        
        // Output  
        if(max_s == "") {
    
            return s.substr(0,1);
        }
        else {
    
            return max_s;
        }
    }
};

4.dp Code （c++）

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        int len=s.size();
        if(len==0||len==1)
            return s;
        int start=0;// Palindrome string start position 
        int max=1;// Maximum length of palindrome string 
        vector<vector<int>>  dp(len,vector<int>(len));// Define a two-dimensional dynamic array 
        for(int i=0;i<len;i++)// Initialization status 
        {
    
            dp[i][i]=1;
            if(i<len-1&&s[i]==s[i+1])
            {
    
                dp[i][i+1]=1;
                max=2;
                start=i;
            }
        }
        for(int l=3;l<=len;l++)//l Indicates the length of the retrieved substring , be equal to 3 Indicates that the first retrieval length is 3 The string of 
        {
    
            for(int i=0;i+l-1<len;i++)
            {
    
                int j=l+i-1;// Stop character position 
                if(s[i]==s[j]&&dp[i+1][j-1]==1)// State shift 
                {
    
                    dp[i][j]=1;
                    start=i;
                    max=l;
                }
            }
        }