[LeetCode] 5. Longest Palindromic Substring

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

 

주어진 문자열에서 가장 긴 팰린드롬 문자열을 반환하라.

 

---

이 문제를 시작으로 하루 종일 팰린드롬 문제만 풀었다.

dp로 해결했는데, 풀기 전에는 어떻게 이걸 dp로 푸나 싶었다.

힌트를 보고 해결 방법이 떠올랐다.

 

어떤 문자열 str이 팰린드롬이라면 이 문자열 str의 앞 뒤에 같은 문자를 추가했을때 그 문자열도 팰린드롬일 것이다.

따라서 문자열에서 특정 위치 left, right의 문자가 같을 때 left+1 ~ right -1 까지의 문자열이 팰린드롬이라면 left ~ right도 팰린드롬일 것이다. 이 특징을 활용해 문제를 해결할 수 있다.

 

dp[left][right] : left~right 까지의 부분 문자열이 팰린드롬인가를 나타내는 boolean 값이라 하자.

우선 한 글자짜리 문자열은 팰린드롬이다. dp[i][i]를 true로 설정해줌과 동시에 연속으로 같은 문자를 갖고 있는 부분 문자열도 처리해주자. str[i] == str[i+1]이면 dp[i][i+1] = true이다. 

 

그 후 left와 right의 차가 2가 되는 지점부터 차례대로 조사한다.

차를 i, 시작점을 j라고 하면 str[j] == str[j + i]일때 이 사이의 문자열도 팰린드롬인지 검사하자.

dp[j+1][j+i-1]이 true라면 dp[j][j + i]도 true가 된다. 

이런식으로 모든 부분 문자열을 조사하며 가장 길이가 긴 부분 문자열을 반환하면 된다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/LeetCode/Longest%20Palindromic%20Substring%202%ED%8A%B8.cpp

chosh95/STUDY

 

 

C++ 코드

#include <string>
#include <iostream>
#include <memory.h>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";

        bool dp[1001][1001];
        memset(dp, false, sizeof(dp));

        string answer = "";

        for (int i = 0; i < s.size(); i++) {
            dp[i][i] = true;
            if (answer.empty()) answer = s.substr(i, 1);
            if (i == s.size() - 1) break;
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                if (answer.length() < 2) answer = s.substr(i, 2);
            }
        }

        for (int i = 2; i < s.size(); i++)
            for (int j = 0; j + i < s.size(); j++)
                if (s[j] == s[j + i] && dp[j + 1][j + i - 1]) {
                    dp[j][j + i] = true;
                    if (answer.length() < i + 1) {
                        answer = s.substr(j, i + 1);
                    }
                }


        return answer;
    }
};

int main()
{
    Solution s;
    cout << s.longestPalindrome("cbbd");
}