[LeetCode] 5. Longest Palindromic Substring

대충 30분 가량 소요..

 

substr에 length에 문자열 연산을 마구잡이로 쓰다보니 TLE 무지막지하게 났다.

 

게다가 stack을 써서 push pop 하면서 LPS 를 판단했었는데 굳이 왜그랬나 싶다.

 

좌 우 index를 가지고 비교하도록 개선하다 보니 성능이 점점 나아졌다.

 

class Solution {
public:
    string longestPalindrome(string s) 
    {
        
        auto size = s.length();
        
        string lps;
        int max_length = 0;
        
        for ( int i = 0; i < size ; i++ )
        {            
            
            if ( size - i < max_length )
                break;
            
            for ( int j = size - i ; j > 0; j--)
            {
                if ( s[i] != s[i + j - 1] )
                    continue;         
                
                if ( j < max_length )
                    continue;       
                                
                int size_substring = j;
                int mid =  size_substring/2 + 1;                
                bool is_lps = true;
                
                for ( int left_index = 0; left_index < mid; ++left_index )                   
                {
                    int right_index = size_substring - left_index - 1;
                    
                    if ( left_index > right_index )
                        break;
                    
                    if ( s[ i + left_index] != s[ i + right_index] )
                    {
                        is_lps = false;
                        break;
                    }
                }
                
                if ( is_lps && max_length < size_substring )
                {
                    lps = s.substr( i, j );                    
                    max_length = size_substring;
                }
                    
            }            
        }
        return lps;        
    }
};

 

 

 

문제출처 : leetcode.com/problems/longest-palindromic-substring