[leetcode 5] Longest Palindromic Substring

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a" Output: "a"

Example 4:

Input: s = "ac" Output: "a"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case),

문제:

가장 긴 palindrome을 찾는 문제. palindrome은 거꾸로 해도 똑같은 문자열이다.

 

풀이:

- 처음 접근: 인덱스 0부터 슬라이딩 윈도우를 써야하나 생각했으나 예외가 너무 많은 거 같아서 패스

- 인덱스를 중심으로 왼쪽, 오른쪽으로 문자열을 확장하는 방식을 사용

- 확장 시에 문자 한 개에서 출발하는지, 문자 두 개에서 출발하는지를 구분해줘야 한다.

- 처음 풀이는 TLE가 났다.... 매번 문자열을 갱신해줬기 때문.

 

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if(len < 2){
            return s;
        }
        
        string result = "";
        string odd, even;
        
        for(int i=0; i<len-1; i++){
           odd = s[i];
            
            // odd length
            for(int left=i-1, right=i+1; left>-1 && right <len; left--, right++){
                if(s[left] == s[right]){
                    odd = s[left] + odd + s[right];
                }else {
                    break;
                }
            }
            if(result.length() < odd.length()){
                result = odd;
            }
            
            // even length
            even = s[i];
            if(s[i] == s[i+1]){
                even += s[i+1];
                for(int left=i-1, right=i+2; left>-1 && right <len; left--, right++){
                    if(s[left] == s[right]){
                        even = s[left] + even + s[right];
                    }else {
                        break;
                    }
                }
                 if(result.length() < even.length()){
                    result = even;
                }
            }
        }
        return result;
    }
};

 

- 답을 봤더니 로직은 유사했으나 문자열이 아닌 인덱스만 저장/업뎃한다는 차이가 있었다. 

- 맞은 코드

class Solution {
public:
    string longestPalindrome(string s) {
        
        int len = s.length();
        if(len < 2){
            return s;
        }
  
        string result = "";
        int start = 0, end = 0;
        
        for(int i=0; i<len-1; i++){
            int maxLen = 0;
            
            // odd length
            int left, right;
            for(left=i-1, right=i+1; left>-1 && right <len; left--, right++){
                if(s[left] != s[right]){
                    break;
                }
            }
            maxLen = right - left - 1;
           
            // even length
            for(left=i, right=i+1; left>-1 && right <len; left--, right++){
                if(s[left] != s[right]){
                    break;
                }
            }
            maxLen = max(maxLen, right-left-1);
            if(maxLen > end-start){ // 기존에 저장되어 있는 최대 길이보다 크다면
                start = i-(maxLen-1)/2;
                end = i + maxLen/2;
            }
        }
        result = s.substr(start, end-start+1);
        return result;
    }
};