Leetcode - 5. Longest Palindromic Substring

문자열이 주어질때 substring중 가장 긴 길이의 palindrome 문자열(좌/우에서 읽어도 동일한 문자열)을 구하라.

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

https://leetcode.com/problems/longest-palindromic-substring/

풀이

중앙에서부터 체크하는 방식. palindrome이 길이가 짝수인것도 있고 홀수인 것도 있으니 둘다 체크해서 더 긴걸로 선택.
230819 다시 풀음.

class Solution {
public:
    string pal_from_middle(string s, int l, int r) {
        while (l >= 0 && r < s.length() && s[l] == s[r]) {
            l--;
            r++;
        }
        l++;
        r--;
        return s.substr(l, r - l + 1);
    }
    string longestPalindrome(string s) {
        string ret;
        for (int i = 0; i < s.length(); i++) {
            string larger = "";
            string odd = pal_from_middle(s, i, i);
            string even = pal_from_middle(s, i, i + 1);
            larger = odd.length() > even.length() ? odd : even;
            ret = larger.length() > ret.length() ? larger : ret;
        }
        return ret;
    }
};

---

아래는 예전에 풀었던 풀이

해결 O(N^2)

문자열을 처음부터 끝까지 순회하면서 각각의 자리에서 expand를 하여 체크,

• 각각의 자리에서 가장 큰 길이의 palindrome 을 찾고 업데이트
• expand_around_center() 함수로 길이가 짝수인경우 홀수인경우 두가지 모두 체크
• 가장긴 길이를 찾았을때 업데이트하는 start, end공식은 짝/홀일때 모두 적용되는 공식...(!)

int expand_around_center(char *str, int left, int right, int ssize)
{
    int len = 0;
    while (left >= 0 && right < ssize && str[left] == str[right]) {
        len = right - left + 1;
        left--;
        right++;
    }
    return len;
}

char *longestPalindrome(char * s){
    int cur_len = 0;
    int len_odd = 0;
    int len_even = 0;
    int start = 0, end = 0;
    int ssize = strlen(s);
    
    for (int i = 0; i < ssize; i++) {
        len_odd = expand_around_center(s, i, i, ssize);
        len_even = expand_around_center(s, i, i+1, ssize);
        cur_len = len_odd > len_even ? len_odd: len_even;
        if (cur_len > end - start + 1) {
            // if current position has more larger palindrome, update start/end index
            start = i - ((cur_len - 1) / 2); // this calc is works for both of odd/even case
            end = i + (cur_len / 2);
        }
    }
    cur_len = end - start + 1;
    char *ret = (char *)malloc(sizeof(char) * (cur_len + 1));
    for (int i = 0; i < cur_len; i++)
        ret[i] = s[start++];
    ret[cur_len] = '\0';
    return ret;
}

해결 brute force O(N^3)

모든범위의 경우의수로 체크 -> TLE 발생.

bool check_palin(char *str, int st, int end)
{
    while (st <= end) {
        if (str[st++] != str[end--])
             return false;
    }
    return true;
}

char *longestPalindrome(char * s){
    int max_len = 1;
    int max_i = 0;
    int ssize = strlen(s);
    
    for (int i = 0; i < ssize; i++) {
        for (int j = i + 1; j < ssize; j++) {
            if (check_palin(s, i, j)) {
                if (j - i + 1 > max_len) {
                    max_len = j - i + 1;
                    max_i = i;
                }
            }
        }
    }
    char *ret = (char *)malloc(sizeof(char) * (max_len + 1));
    for (int i = 0; i < max_len; i++)
        ret[i] = s[max_i++];
    ret[max_len] = '\0';
    return ret;
}