[leetcode] 72. Edit Distance

문제 설명

링크
insert / delete/ replace 를 통해 문자열1을 문자열2로 만드는 가장 간단한 방법의 단계 수 구하기

접근 1 - DP 2차원

• dp[i][j] = word1[:i+1] 과 word[:j+1]
• dp[0][j] = j 빈문자열을 j 로 만드는 방법 = j 번 추가
• dp[i][0] = i i를 빈문자열로 만드는 방법 = i 번 삭제
• word1[i] == word2[j] => dp[i+1][j+1] = dp[i][j]
• word1[i] != word2[j] => dp[i+1][j+1] = (끝자리 기준)
  • replace dp[i][j]
    • horse / ros -> horss / ros ~> hors 와 ro 비교
  • delete dp[i][j+1]
    • horse / ros -> hors / ros ~ > hors와 ros 비교
  • insert dp[i + 1][j]
    • horse / ros -> horses / ros ~> horses와 ro 비교
• space O(mn)

# dp[i+1][j+1]
dp[i+1][j+1] = dp[i][j] if word1[i]==word2[j] 
			else min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1 
# 1은 cost

• dp 계산시 2개의 row 만을 사용하므로 1차원 dp 로 줄일 수 있음

코드 1

def minDistance(word1, word2):
	m, n = len(word1), len(word2)
	dp = [list(range(n+1))]+[[r+1]+[0]*n for r in range(m)]
	for i in range(m):
		for j in range(n):
			dp[i+1][j+1] = dp[i][j] if word1[i]==word2[j] else min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1
	return dp[m][n]

접근 2 - 1차원 DP

• space O(min(m,n))

코드 2

def minDistance(word1, word2):
	m, n = len(word1), len(word2)  # switch word1 and word2 if m < n to ensure n ≤ m
	curr = list(range(n+1))
	for i in range(m):
		prev, curr = curr, [i+1] + [0] * n
		for j in range(n):
			curr[j+1] = prev[j] if word1[i] == word2[j] else min(curr[j], prev[j], prev[j+1]) + 1
	return curr[n]