583. Delete Operation for Two Strings

풀이

LCS를 구할 수 있다면 바로 풀수있는 문제다!
두 스트링이 같아지기 위해, 최소한만 삭제하라는 문제인데, 두 스트링의 LCS를 구하고, 각각 LCS와 얼마나 차이가 나는지만 계산하면 된다.

이전 포스팅 [JavaScript] 1143. Longest Common Subsequence 에 나온 방법과 똑같다.

Time, Space

LCS를 구하는데에 드는 비용과 같다. 따라서 time O(N^2), space O(N^2)이다.

var minDistance = function(w1, w2) {
    if(w1===w2) return 0;
    
    w1 = "#"+w1;
    w2 = "#"+w2;
    const dp = [...Array(w1.length)].map(row => Array(w2.length).fill(0));
    
    for(let i=1; i<w1.length; i++){
        for(let j=1; j<w2.length; j++){
            if(w1[i]===w2[j]){
                dp[i][j] = 1 + dp[i-1][j-1];
            }else{
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
            }
        }
    }
    
    const LCS = dp[w1.length-1][w2.length-1];
    
    return (w1.length-1)-LCS + (w2.length-1)-LCS;
};