[LeetCode] 583. Delete Operation for Two Strings

😎풀이

1. DP 초기화
   1-1. word1의 i까지의 범위와 word2의 j까지의 범위의 최장 공통 부분 수열(LCS) 입력
2. word1과 word2의 LCS 확인
   2-1. 2중 반복하며 word1[i] === word2[j]인 경우, dp[i - 1][j - 1] + 1
   2-2. word1[i] !== word2[j]인 경우, dp[i][j - 1]과 dp[i - 1][j]의 LCS 중 최댓값
3. 두 문자열의 길이에서 LCS를 뺀 값이 제거해야할 문자의 수

function minDistance(word1: string, word2: string): number {
    const n = word1.length
    const m = word2.length
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0))
    for(let i = 1; i <= n; i++) {
        for(let j = 1; j <= m; j++) {
            if(word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    const lcs = dp[n][m]
    return n - lcs + m - lcs
};