[LeetCode] 5. Longest Palindromic Substring (C++)

문제

문자열 s가 주어졌을 때, 가장 긴 palindromic substring찾기

생각할 것

💡 Palindrome

회문, 거꾸로 읽어도 동일한 문자열

 

모든 경우의 수를 브루트포스 방식으로 확인하면 시간복잡도가 O(n^3)이다.

처음에는 현재 문자열을 앞으로 넣고, 뒤로 넣어서 비교해야하나?라고 생각했다.

하지만 이렇게하면 모든 경우 비교가 불가능하다…

결국, 최적의 코드를 위해서는 DP를 사용해야 한다.

1. 가장 먼저 기본 조건을 설정한다.
   1. 길이가 1인 문자열은 모두 팰린드롬.
   2. 길이가 2인 문자열은 두개가 같은 문자인 경우 팰린드롬
2. 그리고 팰린드롬 양쪽에 같은 문자가 추가되면 그 역시도 팰린드롬이라는 점을 이용하기!

시간복잡도는 O(N^2)가 된다.

 

예제1. babad

 

예제2. cbbd

 

 

예제3. cbbc

결과 코드

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size()));
        string res;
        int maxLen;

        // base
        for(int i=0; i<s.size(); i++){ // 문자 길이가 1인 경우 : 반드시 팰린드롬
            dp[i][i] = true;
            res = s[i];
            maxLen = 1;
        }

        for(int i=0; i<s.size()-1; i++){ // 문자 길이가 2인 경우 : 두 문자의 값이 같으면 팰린드롬
            if(s[i] == s[i+1]){
                dp[i][i+1] = true;
                res = s.substr(i, 2);
                maxLen = 2;
            }
        }

        // dp
        for(int len=2; len<=s.size(); len++){ // 팰린드롬의 왼쪽, 오른쪽에 같은 문자가 추가되면 팰린드롬
            for(int i=0; i<s.size() - len + 1; i++){
                int j = i + len - 1;
                if(dp[i+1][j-1] && s[i] == s[j]){ 
                    dp[i][j] = true;
                    if(len > maxLen){
                        res = s.substr(i,len);
                        maxLen = len;
                    }
                }
            }
        }

        return res;
    }
};