(Leet Code JS)Delete Operation for Two Strings

https://leetcode.com/problems/delete-operation-for-two-strings/

Delete Operation for Two Strings - LeetCode

 

LCS와 DP 를 이용한 문제풀이.

 

우선 주어진 두 문자열이 같다면 지울 필요가 없기 때문에 0을 바로 리턴한다.

그렇지 않다면 LCS를 확인.

 

두 문자열 중 길이가 더 긴 문자를 word1에 저장한다.

변수는 word1의 길이와 word2의 길이를 저장하는

word1Len, word2Len.

DP 테이블에 해당하는 dp 가 있다.

 

for문을 돌면서 LCS를 갱신한다.

LCS의 점화식은 다음과 같다.

 

문자열 X, Y가 있으며, i, j는 인덱스를 나타낸다.

 

if Xi === Yj :

dp[i][j] = dp[i - 1][j - 1] + 1

 

if Xi !== Yj:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

 

이를 이용해서 DP 테이블을 채운다.

DP 테이블에서 가장 마지막에 존재하는 수가 LCS의 길이에 해당한다.

리턴값은 각 문자열의 길이에서 LCS의 길이를 뺀 값을 더하면 된다.

var minDistance = function(word1, word2) {
    let lcs = 0;
    
    if(word1 === word2){
        return 0;
    }

    if(word1.length < word2.length){
        [word1, word2] = [word2, word1];
    }
    
    const word1Len = word1.length;
    const word2Len = word2.length;
    const dp = Array.from({length: word1Len + 1}, () => Array(word2Len + 1).fill(0));

    for(let i = 1; i <= word1Len; i++){
        for(let j = 1; j <= word2Len; j++){
            const char1 = word1[i - 1];
            const char2 = word2[j - 1];
            
            if(char1 === char2){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    lcs = dp[word1Len][word2Len];
    
    return (word1Len - lcs) + (word2Len - lcs);
};