1312. Minimum Insertion Steps to Make a String Palindrome

1312. Minimum Insertion Steps to Make a String Palindrome

 

class Solution:
    def minInsertions(self, s: str) -> int:
        # Palindrome: 앞뒤로 읽었을때 동일한 string
        # 최소로 추가해야 하는 문자 개수를 반환
        # 이미 Palindrome 이면 0 반환
        
        # 그럼 우선 Palindrome 인지 체크하고
        if s == s[::-1]: # Palindrome 이면
            return 0

        # 아니면
        # s 와 뒤집은 s, 즉 reverse_s 의 LCS 최고로 긴 공통 문자열 찾아서, 
        # 전체 len(s) - les(LCS) 하면 될듯
        reverse_s = s[::-1]
        ln_s = len(s)
        ln_rev_s = len(reverse_s)

        dp = [[0] * (ln_s+1) for _ in range(ln_rev_s+1)]
        for i in range(1, ln_s+1):
            for j in range(1, ln_rev_s+1):
                if s[i-1] == reverse_s[j-1]:
                    dp[i][j] = dp[i-1][j-1] +1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return len(s) - dp[-1][-1]