[LeetCode] 712. Minimum ASCII Delete Sum for Two Strings

😎풀이

1. dp 배열 생성, s1의 i번째 요소 및 s2의 j번째 요소까지 탐색하는 경우로 산정
2. s1이 빈 문자열인 경우와 s2가 빈 문자열인 경우를 가정해 모든 문자를 제외하는 경우를 초기화
3. 문자를 순회하며 dp 채우기
   3-1. s1과 s2의 문자가 같은 경우, 제거 비용이 들지 않음
   3-2. s1과 s2의 문자가 다른 경우, 이전까지의 비용 + s1과 s2 둘 중 하나를 제거한 비용 중 더 낮은 비용 채택
4. 동일한 문자열을 구성하기 위해 필요한 최소 ASCII 값 반환

function minimumDeleteSum(s1: string, s2: string): number {
    const m = s1.length
    const n = s2.length
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0))
    
    for(let i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] + s1.charCodeAt(i - 1)
    }
    for(let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] + s2.charCodeAt(j - 1)
    }

    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            if(s1[i - 1] === s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
                continue
            }
            const s1Del = dp[i - 1][j] + s1.charCodeAt(i - 1)
            const s2Del = dp[i][j - 1] + s2.charCodeAt(j - 1)
            dp[i][j] = Math.min(s1Del, s2Del)
        }
    }

    return dp[m][n]
};