当前位置:网站首页>Leecode05. Longest palindrome substring -- leecode100 question series

Leecode05. Longest palindrome substring -- leecode100 question series

2021-10-14 05:05:53 Old fellow iron has dried up the code.

I'm Xiao Zhang , Determined to use the most concise code to do the most efficient expression


The following is my personal solution , Each problem includes all solutions as much as possible , And achieve the optimal solution , Welcome to collect ! Leaving a message. !

Answer key classification
Leecode01. Sum of two numbers (C++) hash
Leecode02. Addition of two numbers (C++) Linked list
Leecode03. Longest substring without repeating characters (C++) hash + The sliding window

Problem description

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

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

Example 2:
Input :s = “cbbd”
Output :“bb”

Example 3:

Input :s = “a”
Output :“a”

Example 4:
Input :s = “ac”
Output :“a”

Tips :
1 <= s.length <= 1000
s Just numbers and letters ( Capital and / Or lowercase ) form


Ideas

Center detection method ( Common methods for solving palindrome strings )


Complexity analysis

Time complexity O ( n 2 ) O(n^2) O(n2), among n n n Is the length of the string . The length is 1 1 1 and 2 2 2 The palindrome centers are n n n and n − 1 n-1 n1 individual , Each palindrome center will expand outward at most O ( n ) O(n) O(n) Time .

Spatial complexity O ( 1 ) O(1) O(1).


Code 1 ( Universal code )

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        int left = 0, right = s.length() - 1;
        int maxLen = 0, nowLen = 0;
        string res = "";
        for(int i = 0; i < s.length(); i++) {
    
            //  Palindrome sequence is odd 
            nowLen = 1;
            int l = i-1, r = i+1;
            while (l >= left && r <= right) {
    
                if(s[l] == s[r]) {
    
                    nowLen += 2;
                } else {
    
                    break;
                }
                l--; r++;
            }
            if(nowLen > maxLen) {
    
                maxLen = nowLen;
                res = s.substr(l+1, maxLen);
            }

            //  Palindrome sequence is even 
            nowLen = 0;
            l = i, r = i+1;
            while (l >= left && r <= right) {
    
                if(s[l] == s[r]) {
    
                    nowLen += 2;
                } else {
    
                    break;
                }
                l--; r++;
            }
            if(nowLen > maxLen) {
    
                maxLen = nowLen;
                res = s.substr(l+1, maxLen);
            }
        }
        return res;
    }
};

Code 2: Function reuse

class Solution {
    
public:
    int func(int& nowLen, int l, int r, string s) {
    
        while (l >= 0 && r <= s.length()) {
    
            if(s[l] == s[r]) {
    
                nowLen += 2;
            } else {
    
                break;
            }
            l--; r++;
        }
        return l;
    }
    string longestPalindrome(string s) {
    
        int maxLen = 0, nowLen, sta;
        string res = "";
        for(int i = 0; i < s.length(); i++) {
    
            //  Palindrome sequence is odd 
            nowLen = 1;
            sta = func(nowLen, i-1, i+1, s);
            if(nowLen > maxLen) {
    
                maxLen = nowLen;
                res = s.substr(sta+1, maxLen);
            }

            //  Palindrome sequence is even 
            nowLen = 0;
            sta = func(nowLen, i, i+1, s);
            if(nowLen > maxLen) {
    
                maxLen = nowLen;
                res = s.substr(sta+1, maxLen);
            }
        }
        return res;
    }
};


When you think you're smart , When everyone starts praising you , In fact, you are just harvesting your previous accumulation .

版权声明
本文为[Old fellow iron has dried up the code.]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/10/20211002145845260h.html

随机推荐