72. Edit Distance

[개발뉴비(coderhs)]

class Solution:

    def minDistance(self, word1: str, word2: str) -> int:

        N, M = len(word1), len(word2)

        dp = [[0 for _ in range(M+1)] for _ in range(N+1)]

        for n in range(N+1): dp[n][0] = n

        for m in range(M+1): dp[0][m] = m

        for m in range(1,M+1):

            for n in range(1,N+1):

                if word1[n-1] == word2[m-1]:

                    dp[n][m] = dp[n-1][m-1]

                else:

                    dp[n][m] = min(dp[n-1][m], dp[n][m-1], dp[n-1][m-1])+1

        return dp[N][M]

엄청 어렵게 느꼈음. 내가 DP 유형을 많이 안 풀어본 탓이 크고..

백준에서 같은 문제가 골드3인걸 보면 아무래도 DP 빈출유형일 확률이 높음.

자연어 처리에서 레벤슈타인 거리라는걸 배웠는데 그거 관련인듯?

https://www.acmicpc.net/problem/15483

Baekjoon Online Judge