Daily LeetCode Challenge - 516. Longest Palindromic Subsequence

Problem From.
https://leetcode.com/problems/longest-palindromic-subsequence/

오늘 문제는 주어진 string s 에서 0개 이상의 알파벳을 지웠을때, 가장 큰 palindrome 을 찾는 문제였다.

이 문제는 dp 로 풀 수 있었는데, 먼저 조건들을 찾아내야 했다.
이차원 배열의 memo 배열을 선언해두고 memo[i][j] 에서 i 는 시작점 j 는 끝점으로 가정한다면
i == j 일때, 길이가 1 인 알파벳은 palindrome 이므로 값은 1 이 된다.
s[i] == s[j] 일때는 memo[i][j] 의 값은 그 전의 memo[i-1][j] + 2 가 된다. 두개의 알파벳이 같다면 길이가 2 인 palidrome 이 만들어지기 때문에 그 전의 값에 2를 더하게 된다.
s[i] != s[j] 인 경우에는 s[i] 를 포함시키고 s[j] 를 빼거나 s[i] 를 빼고 s[j] 를 포함시켜야 하므로 각각의 경우의 최대값을 구하기 위해 Math.max(memo[i+1][j], memo[i][j-1]) 의 값을 가지게 된다.

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val memo = Array(s.length) { IntArray(s.length) }
        for(diff in 0 until s.length) {
            for(i in 0 until s.length) {
                val j = i + diff
                if(j >= s.length) continue
                memo[i][j] = when(j) {
                    i -> 1
                    i + 1 -> if(s[i] == s[j]) 2 else 1
                    else -> if(s[i] == s[j]) 2 + memo[i+1][j-1] else Math.max(memo[i+1][j], memo[i][j-1])
                }
            }
        }
        return memo[0][s.length - 1]
    }
}