개발자 Lim

<접근 방법> 

LCS

문자열 S와 문자열 S를 뒤집은 reverse_S을 대상으로

DP를 기반으로 한 LCS 최장 공통 부분수열(Longest Common Subsequence) 알고리즘을 사용하여

최장 공통 부분의 길이(n)를 구하고 

s.length() -  n을 반환

<자세한 설명 링크>

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

<풀이 코드>

class Solution {
    // 시간 복잡도 O(n^2) 공간 복잡도 O(n^2)
    public int minInsertions(String s) {
       int n = s.length();
       int[][] dp = new int[n+1][n+1];
       // LCS ALG
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(s.charAt(i)==s.charAt(n-1-j))
                    dp[i+1][j+1] = dp[i][j]+1;
                else
                    dp[i+1][j+1] = Math.max(dp[i+1][j],dp[i][j+1]);
            }
        }
        return n-dp[n][n];
    }
}