•
문제 링크 : 
LeetCodeEdit Distance - LeetCode
•
문제 설명 : 최소 편집 거리 알고리즘을 사용한다.
•
풀이 방법
◦
편집 거리(Edit Distance)는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소한의 편집 연산(삽입, 삭제, 대체)의 횟수을 말한다.
◦
두 문자열이기 때문에, 2차원 배열을 사용하여 구한다.
◦
▪
여기서, 연산을 구하는 부분이 이해가 되지 않을 수 있다.
•
dp[i][j-1] + 1 : 삽입 방식이다.
◦
[i]는 word1[i](word1 현재 문자), [j-1] 은 word2[j-1](word2 이전 문자) 이다.
◦
word1의 현재 문자가 word2의 이전 문자와 같다면, 삽입으로 처리하는 것이다.
•
dp[i-1][j] + 1 : 삭제 방식이다.
◦
word1의 이전 문자가 word2의 현재 문자와 같다면, word1의 현재 문자를 삭제하는 방식이다.
•
dp[i - 1][j - 1] + (word1[i] != word2[j]) : 교체 방식이다.
◦
word1의 현재 문자와 word2의 현재 문자가 다른 경우, 교체 작업을 하는 방식이다.
▪
만약 dp[i][j]를 구한다면, 위 3개중 작은 값을 추가하면 된다.
•
시간복잡도 :
•
성공 코드
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
dp = [[float(inf) for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(m + 1):
dp[0][i] = i
for i in range(n + 1):
dp[i][0] = i
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = min(
# 삽입
dp[i - 1][j] + 1,
# 삭제
dp[i][j - 1] + 1,
# 편집
dp[i - 1][j - 1] + (word1[i - 1] != word2[j - 1])
)
return dp[-1][-1]
Python
복사