712. Minimum ASCII Delete Sum for Two Strings ★★

712. Minimum ASCII Delete Sum for Two Strings

 

이 문제는 두 문자열을 같게 만들기 위해 삭제해야 하는 문자들의 ASCII 값 합을 최소화하는 문제입니다. 이를 해결하기 위해 **동적 계획법(Dynamic Programming)**을 사용할 수 있습니다.

---

문제 분석

1. 주어진 문자열:
   • s1="sea", s2="eat"
2. 목표:
   • 두 문자열을 같게 만들기 위해 삭제해야 하는 문자의 ASCII 값 합을 최소화.
   • 공통된 부분 수열은 유지하고 나머지 문자는 삭제.
3. 예제 분석:
   • s1="sea", s2="eat"
     • 공통된 부분 수열은 "ea".
     • 삭제된 문자들:
       • s1: "s"(115)
       • s2: "t" (116)
     • 결과: 115+116=231.

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        # 부분 공통 수열 집합 찾아서, 아스키 구해서 최소값
        # Find the lowest ASCII sum of deleted characters to make s1 and s2 equal
        M, N = len(s1), len(s2)  # s1의 길이 M, s2의 길이 N 계산 / Calculate lengths of s1 and s2

        # DP 테이블 생성: dp[m][n]은 s1[0:m]과 s2[0:n]을 같게 만들기 위해 삭제해야 하는 최소 ASCII 값 합
        # Create a DP table: dp[m][n] represents the minimum ASCII sum of deletions to make s1[0:m] and s2[0:n] equal
        dp = [[0] * (N + 1) for _ in range(M + 1)]

        # init
        for m in range(1, M + 1):  # s1의 모든 문자에 대해 / For all characters in s1
            dp[m][0] = dp[m - 1][0] + ord(s1[m - 1])  
            # dp[m][0]: s1[0:m]의 모든 문자를 삭제해야 하므로 누적 아스키 값 계산
            # dp[m][0]: All characters of s1[0:m] are deleted, so accumulate their ASCII values
            # ord(문자) = 아스키값, 누적해서 더함 / ord(character) gives the ASCII value, which is accumulated

        for n in range(1, N + 1):  # s2의 모든 문자에 대해 / For all characters in s2
            dp[0][n] = dp[0][n - 1] + ord(s2[n - 1])  
            # dp[0][n]: s2[0:n]의 모든 문자를 삭제해야 하므로 누적 아스키 값 계산
            # dp[0][n]: All characters of s2[0:n] are deleted, so accumulate their ASCII values

        for m in range(1, M + 1):  # s1의 각 문자에 대해 (1부터 M까지) / For each character in s1 (from 1 to M)
            for n in range(1, N + 1):  # s2의 각 문자에 대해 (1부터 N까지) / For each character in s2 (from 1 to N)
                if s1[m - 1] == s2[n - 1]:  # 두 문자가 같다면 / If the two characters are the same
                    dp[m][n] = dp[m - 1][n - 1]  
                    # 같은 문자는 삭제하지 않아도 되므로 이전 상태(dp[m-1][n-1])를 그대로 가져옴
                    # If the characters are the same, no deletion is needed, so inherit dp[m-1][n-1]
                else:  # 두 문자가 다르다면 / If the two characters are different
                    dp[m][n] = min(
                        dp[m - 1][n] + ord(s1[m - 1]),  # s1의 현재 문자 삭제 / Delete the current character from s1
                        dp[m][n - 1] + ord(s2[n - 1])   # s2의 현재 문자 삭제 / Delete the current character from s2
                    )
                    # 두 경우 중 ASCII 값 합이 최소가 되는 경우를 선택
                    # Choose the option with the minimum ASCII sum

        return dp[-1][-1]  # dp[M][N] 반환, 최종 결과: s1과 s2를 같게 만들기 위한 최소 ASCII 값 합
        # Return dp[M][N], which is the minimum ASCII sum of deletions to make s1 and s2 equal