Daily LeetCode Challenge - 1312. Minimum Insertion Steps to Make a String Palindrome

Problem From.
https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

오늘 문제는 string S 가 주어질때, 그 string 에 최소갯수의 임의의 글자를 추가해서 그 글자를 palindrome 으로 만드는 문제였다.

이 문제는 DP 를 이용해서 풀 수 있었는데,
글자의 맨 앞과 맨 뒤를 비교하여, 글자가 같으면 넘어가고, 글자가 같지 않으면 i 의 -1 즉 앞글자 쪽에 한 글자를 추가하거나 j 의 -1 즉 뒷글자쪽에 한글자를 추가한것의 최대값을 가져와서 다시 넣어주는 식으로 반복하였다. 반복이 끝나면 memo 배열의 맨 끝값을 가져오면 된다.

class Solution {
    fun minInsertions(s: String): Int {
        val s2 = s.reversed()

        val memo = Array(s.length + 1){IntArray(s.length + 1)}
        for (i in 1 .. s.length) {
            for (j in 1 .. s.length) {
                memo[i][j] = if (s[i-1] == s2[j-1]) {
                    memo[i-1][j-1]+1
                } else {
                    maxOf(memo[i-1][j], memo[i][j-1])
                }
            }
        }
        return s.length - memo[s.length][s.length]
    }
}