Leetcode - Longest Palindromic Subsequence

문제 출처: https://leetcode.com/problems/longest-palindromic-subsequence/

문제 설명

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"

Output: 4

Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"

Output: 2

Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

문제 풀이

class Solution {
    
    static Integer [][] cache;
    public int longestPalindromeSubseq(String s) {
        
        cache = new Integer [s.length()][s.length()];
        int answer = findPalindrome(s, s.length() - 1, 0);
        return answer;
        
    }
    
    public static int findPalindrome(String s, int right, int left) {
        
        if(right == left)
            return 1;
        else if(right < left)
            return 0;
        
        if(cache[left][right] == null) {
        
            if(s.charAt(left) == s.charAt(right)) {
                cache[left][right] =  2 + findPalindrome(s, right - 1, left + 1);
            } else {
                cache[left][right] = Math.max(findPalindrome(s, right - 1 , left), findPalindrome(s, right, left + 1));
            }
        }
        return cache[left][right];
    }
}

풀이 방법

일단 재귀적으로 문자열의 맨앞뒤 인덱스에 포인터를 만들고 증감시키면서 팰린드롬인지 확인하는 알고리즘을 생각 해야한다. 하지만 재귀함수로만 구현을 하면 같은 연산을 반복해서 하기 때문에 메모이제이션을 해주어서 중복 연산을 제거해야 하기 때문에 결과적으로 동적 계획법으로 풀이해야 맞다.

참고 자료: https://ssminji.github.io/2020/02/05/the-cake-thief/