[C] LeetCode 516. Longest Palindrome Subsequences

문제

번역

문자열 s가 주어졌을때, 가장 긴 팰린드롬 부분배열의 길이를 반환해라.

여기서 부분배열이란, 원래 문자열에서 일부 문자를 지우거나 지우지 않아서 만들 수 있는 수열이다.

일부 문자를 지워도 남아있는 문자들의 순서는 바뀌면 안 된다.

 

접근 방법 및 소스코드

문자열 전체를 보지 않고 작은 구간부터 찾아가면 된다.

dp[i][j] 는 문자열 i번째부터 j번째까지의 구간에서 만들 수 있는 가장 긴 팰린드롬 부분배열의 길이라고 하자.

 

양 끝 문자가 같다면 이 둘은 팰린드롬의 양 끝으로 같이 쓸 수 있다.

그러면 안쪽 구간에서 만든 가장 긴 팰린드롬에다가 양쪽 문자 2개를 더하면 된다.

 

양 끝 문자가 다른 경우 둘 다 쓸 수 없다.

그래서 왼쪽 문자 i를 버리거나 오른쪽 문자 j를 버려야 한다.

이 둘 중 하나를 버렸을때 더 큰값을 선택하면 된다.

 

int max(int a, int b) { return (a<b)?b:a;}
int longestPalindromeSubseq(char* s) {
    int len = strlen(s);
    int dp[1000][1000] = {0,};

    for(int i=0;i<len;i++) dp[i][i] = 1;

    for(int i=len-1;i>=0;i--) {
        for(int j=i+1; j<len; j++) {
            dp[i][j] = (s[i] == s[j]) ? dp[i+1][j-1]+2 : max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][len-1];
}