[Leetcode] 5. Longest Palindromic Substring

문제

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 <= 1000s consist of only digits and English letters.

 

풀이

palindrome의 시작이 되는 곳을 s의 처음부터 하나씩 구해준다.

이때 s[i]==s[i+1], s[i-1]==s[i+1] 경우 둘다 고려해줘야 한다.

 

중요한점은 while loop 에서 인덱스를 먼저 condition으로 둬야 다음 s[left] == s[right] 비교할때 index out of bound 에러가 뜨지 않는다.

 

코드

char* longestPalindrome(char* s) {
    int size = strlen(s);
    if(size == 1) return s;

    int maxlen = 1;
    int index = 0;

    for(int i = 0; i < size; i++) {
        int left = i, right = i, len = 0;
       
        while( left >= 0 && right < size && s[left] == s[right] ) { // left & right condition first!
            len = right-left+1;
            if(maxlen < len) {
                maxlen = len;
                index = left;
            }
            left--;
            right++;
        }

        left = i, right = i+1, len = 0;
       
        while( left >= 0 && right < size && s[left] == s[right] ) { // left & right condition first!
            len = right-left+1;
            if(maxlen < len) {
                maxlen = len;
                index = left;
            }
            left--;
            right++;
        }
    }
    char* result = (char*)malloc((maxlen+1) * sizeof(char));
    strncpy(result, s+index, maxlen);
    result[maxlen] = '\0';
    
    return result;
}