문제

Problem

Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
A Palindrome String is one that reads the same backward as well as forward.

Examples

• Input: s = "zzazz"
  Output: 0
  Explanation: The string "zzazz" is already palindrome we do not need any insertions.
• Input: s = "mbadm"
  Output: 2
  Explanation: String can be "mbdadbm" or "mdbabdm".
• Input: s = "leetcode"
  Output: 5
  Explanation: Inserting 5 characters the string becomes "leetcodocteel".

풀이

sub-string으로 나누어, 문자열 길이가 짧은 순서대로 접근하는 방법을 사용합니다.

Input: s = "mbadm" 일 때,
"m", "b", "a", "d", "m"
-> "mb", "ba", "ad", "dm" 
-> "mba", "bad", "adm" 
-> "mbad", "badm" 
-> "mbadm"

이 때 아래 2가지를 적용합니다.

1. 양 끝이 같을 때, 양 끝을 제거한 sub-string과 insertion 횟수가 같습니다.

   "mbadm"과 "bad"는 insertion 횟수가 같습니다. (2회)

2. 양 끝이 다를 때, "맨 앞 문자를 제거한 sub-string"과 "맨 뒷 문자를 제거한 sub-string" 중 가장 작은 insertion 횟수에 1을 더한 값이 가장 작은 insertsion 횟수와 같습니다.

   "aaab"라는 문자열이 있을 때,
   가장 작은 insertion 횟수는 1입니다.
   1) "aaa" + "b" -> "(b)aaab" -> 1회
   2) "a" + "(b)aab" -> "(b)(a)aaab" -> 2회
   이것은 min(insertion("aaa"), insertion("aab")) + 1과 같습니다.

위 규칙을 따라, 알고리즘을 작성하면 다음과 같습니다.

if (s[start] == s[end]) { 
	insertion(s[start:end]) = insertion(s[start+1:end-1])
} else {
	insertion(s[start:end]) = min(insertion(s[start+1:end], insertion(s[start:end-1])) + 1
}

실제 구현한 코틀린 코드는 아래와 같습니다.
sub-string들의 insertion 횟수를 기록하기 위해
2차원 DP를 활용하였습니다.
dp[i][j]는 s의 sub-string인 s[i:j]의 최소 insertion 횟수를 저장합니다.

import kotlin.math.min

class Solution {
    fun minInsertions(s: String): Int {
        var dp = Array(s.length, { IntArray(s.length){ 0 } })

        for (subSize in 2..s.length)  {                     // subSize: substring의 개수
            for (start in 0..s.length-subSize) {            // start: substring이 시작하는 인덱스
                for (end in start+subSize-1..s.length-1) {  // end: substring이 끝는 인덱스
                    if (s[start] == s[end]) {               // 시작과 끝이 같다면,
                        dp[start][end] = dp[start+1][end-1] // substring의 시작과 끝이 없는 경우와 insertion 횟수 같음
                    } else {                                // 다르다면,
                    	// substring[start+1:end] 혹은 substring[start:end-1] 중 적은 횟수에 insertion 횟수 1번 추가
                        dp[start][end] = min(dp[start+1][end], dp[start][end-1]) + 1  
                    }
                }
            }
        }

        return dp[0][s.length-1]
    }
}