Longest Palindromic Substring[M]

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

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

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

Topics: Two Pointers / String/ Dynamic Programming

 

1. Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        temp={}
        for i in range(len(s)):
            for e in range(i,len(s)):
                #check Palidrome
                start = i
                end = e
                while start<=end:
                    if s[start]==s[end]:
                        start+=1
                        end-=1
                    else : break
                if start>end:
                    temp[e-i+1] = s[i:e+1]
        return temp[max(temp)]
        
        """
        이렇게 하니까 아래 test case에서 timelimit이 걸림;;
        "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"
        """

 

좀 더럽지만 이렇게 수정해서 accep됐다.. 너무 더럽기에 다른 솔루션도 참고해야지

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        temp={}
        intmax = -1
        for i in range(len(s)):
            for e in range(len(s)-1,-1,-1):
                #check Palidrome
                start = i
                end = e
                if e-i+1 <= intmax:
                    break
                else:
                    while start<=end:
                        if s[start]==s[end]:
                            start+=1
                            end-=1
                        else : break
                    if start>end:
                        temp[e-i+1] = s[i:e+1]
                        intmax = max(temp)
        return temp[max(temp)]

 

C는 도저히 모르겠다.. 아 진짜 C로 String 다루는 게 너무나 빡세다 증말

 

 

3. C++

 

class Solution {
public:
    string expand_from_center(int left,int right,const string& s){
        while(left >=0 && right < s.length() && s[left] == s[right]){
            left --;
            right ++;
        }
        return s.substr(left+1,right-left-1); // 왼쪽에서~ 오른쪽값 만큼만 substr
    }
    string longestPalindrome(string s) {
        if(s.length()<=1) return s;

        string max_str = s.substr(0,1);
        string odd;
        string even;
        for(int i=0;i<s.length()-1;i++){
            odd = expand_from_center(i,i,s);
            even = expand_from_center(i,i+1,s);

            // max_str = odd.length() > even.length() ? odd : even;
            if(max_str.length() < odd.length()) max_str = odd;
            if(max_str.length() < even.length()) max_str = even;
        }
        return max_str;
    }
};