72. Edit Distance

72. Edit Distance

 

https://youtu.be/XYi2-LPrwm4?si=8R5kcaUc9tWO8sSQ

 

 

 

 

 

초기값 세팅 설명

초기 설정의 의미

• 첫 번째 행과 열은 문자열이 비어 있을 때 작업의 기준점을 제공합니다.
• 이후, 이 값을 기반으로 나머지 테이블 값을 채우며 두 문자열의 변환 비용을 계산합니다.

이후 과정

결론

DP 테이블의 최종 값은 문자열을 변환하는 모든 가능한 경로를 고려해 최적의 변환 비용을 계산한 결과입니다. 이를 통해 삽입, 삭제, 교체 작업을 효율적으로 비교할 수 있습니다.

 

Code

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # DP 테이블 생성
        # cache[i][j]: word1[i:]를 word2[j:]로 변환하는 최소 작업 수
        cache = [[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]
        
        # 초기값 설정
        # word1이 비어 있는 경우: word2[j:]로 변환하기 위해 삽입만 필요
        for j in range(len(word2) + 1):
            cache[len(word1)][j] = len(word2) - j  # 남은 글자 수만큼 삽입

        # word2가 비어 있는 경우: word1[i:]를 비우기 위해 삭제만 필요
        for i in range(len(word1) + 1):
            cache[i][len(word2)] = len(word1) - i  # 남은 글자 수만큼 삭제

        # DP 테이블 계산
        # 역순으로 계산: word1[i:]와 word2[j:]를 고려
        for i in range(len(word1) - 1, -1, -1):  # word1의 끝에서 시작
            for j in range(len(word2) - 1, -1, -1):  # word2의 끝에서 시작
                if word1[i] == word2[j]:  # 두 문자가 같으면 작업 필요 없음
                    cache[i][j] = cache[i + 1][j + 1]
                else:  # 삽입, 삭제, 교체 중 최소 작업 선택
                    cache[i][j] = 1 + min(
                        cache[i + 1][j],     # 삭제: word1[i] 삭제
                        cache[i][j + 1],     # 삽입: word2[j] 삽입
                        cache[i + 1][j + 1]  # 교체: word1[i]를 word2[j]로 교체
                    )

        # 최종 결과: word1[0:]를 word2[0:]로 변환하는 최소 작업 수
        return cache[0][0]

# 예제 실행
solution = Solution()
print(solution.minDistance("horse", "ros"))  # 출력: 3
print(solution.minDistance("intention", "execution"))  # 출력: 5

 

아래 코드로..

 

https://youtu.be/dY_dZohgVa8?si=DGLuMiDNJzl1cj1P

 

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:        
        len1 = len(word1)
        len2 = len(word2)

        # 배열 만들기
        # 결국 답은 dp[len1][len2]
        """
        i 는 1부터 len1 = len(word1) 까지
        j 는 1부터 len2 = len(word2) 까지

        d[i][j]
            word1 의 i 까지의 부분 문자열을  
            word2 의 j 까지의 부분 문자열로 
            교체하기 위한 최소 작업 수

        문자열이 abs -> def 로 주어질때
            d[1][1] 은
            a->d, 즉, a 를 d로 바꾸기 위한 최소 작업수: 1        
        """

        # 배열 생성, +1 꼭 필요
        # 배열 생성시, len1, len2 순서 중요!
        # dp = ([0]*(len2+1)) *(len1+1) <- 이건 2차원 배열 아님
        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

        # 초기화
        # i: word1 의 부분 문자열 이고
        # j: 0  즉, "" 공백 문자열. 이었을때
        # 첫번째 문자열을 공백으로 교체하기 위한 최소 작업수
        # 첫번째 문자열의 단어 길이만큼 필요
        # word1 = "horse" 이면
        # dp[1][0] 은 'h' 와 공백 -> 1글자를 공백으로 -> 작업수 1번 필요
        # dp[2][0] 은 'ho' 와 공백 -> 2글자를 공백으로 -> 작업수 2번 필요
        # dp[3][0] 은 'hor' 와 공백 -> 3글자를 공백으로 -> 작업수 3번 필요
        # .. 이런식
        for i in range(len1 + 1): # 초기화는 +1 꼭 필요
            dp[i][0] = i

        # j: word2 의 부분 문자열
        for j in range(len2 + 1):
            dp[0][j] = j

        # 루프: 1부터 ~ *주의*
        for i in range(1, len1+1): 
            for j in range(1, len2+1):                
                if word1[i-1] == word2[j-1]: 
                    # word1의 i번째 문자와 word2의 j번째 문자가 같으면, 
                    # 메모이제이션 배열에서 대각선 위의 값을 가져오면 됨
                    # 왜냐면, 문자가 같기때문에, 어떤 오퍼레이션이 추가로 필요없음
                    # 그래서, 그 전의 i-1, j-1의 값이 그대로 i,j 값이 됨
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # 문자가 다르면
                    # 추가 작업인
                    # insert, delete, replace 중 하나가 필요하니, 작업이 1 더 더해짐
                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

        # 리턴: 마지막..값으로.. *주의*
        return dp[len1][len2]

 

 

 

https://youtu.be/6jvSfC2-JDo?si=R2jXQFFVxaokuPBW

 

 

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        M, N = len(word1), len(word2)

        dp = [[0] * (N+1) for _ in range(M+1)] # +1 주의
        for m in range(M+1): # +1 주의
            dp[m][0] = m
        for n in range(N+1): # +1 주의 
            dp[0][n] = n

        for m in range(1, M+1): # 1부터 주의
            for n in range(1, N+1): # 1부터 주의
                """
                문자열의 실제 인덱스는 0부터 시작하지만, 
                DP 테이블은 1부터 시작하도록 설정됨
                따라서, dp[m][n]은 문자열의 실제 인덱스 m−1과 n−1을 참조함
                """
                if word1[m-1] == word2[n-1]: # 왜 -1??
                    dp[m][n] = dp[m-1][n-1]
                else:
                    dp[m][n] = min(dp[m-1][n-1], dp[m][n-1], dp[m-1][n]) + 1
        return dp[M][N]