Edit Distance
두 단어 word1과 word2가 주어집니다. 한 번의 편집으로 word1을 다음 세 가지 방법 중 하나로 변경할 수 있습니다. 아무 위치에나 문자를 삽입하거나, 문자를 삭제하거나, 문자를 다른 문자로 바꿉니다. word1을 word2로 바꾸는 데 필요한 최소 편집 횟수를 반환하세요.
함수
- word1string
- 네가 편집하는 단어
- word2string
- 도달하다라는 단어
- 반환값integer
- word1을 word2로 변환하는 데 필요한 삽입, 삭제 및 대체의 최소 횟수
제약 조건
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- 두 단어 모두 소문자 영어 알파벳만 포함합니다.
예제
- 입력
- word1 = "spot"word2 = "stop"
- 출력
- 2
- 설명
- p를 t로, t를 p로 바꾸세요:
spot은stot이 되고, 그다음stop이 됩니다. 한 번의 편집으로는 충분하지 않습니다. 두 단어는 두 곳에서 다르며, 삽입하거나 삭제하면 길이가 달라지기 때문입니다.
- 입력
- word1 = "garden"word2 = "ardent"
- 출력
- 2
- 설명
arden을 얻으려면 g를 삭제한 다음, 끝에 t를 삽입하여ardent를 얻으세요. 글자를 하나씩 바꾸면 두 단어가 모든 위치에서 다르므로 비용이 6입니다.
- 입력
- word1 = "rain"word2 = "shine"
- 출력
- 3
- 설명
- r을 s로, a를 h로 바꾼 다음 e를 삽입하세요. 두 번의 수정으로는 부족합니다. r과 a는
shine에 없으므로 각각 길이를 유지하는 수정이 필요하고, 단어는 여전히 한 글자 늘어나야 합니다.
후속 질문
편집 횟수와 함께 편집 내용의 가장 짧은 목록 하나도 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
각 단어의 마지막 글자를 살펴보세요. 글자가 같다면, 이를 건드려야 할까요? 다르다면, 두 단어가 같은 방식으로 끝나도록 어떤 편집을 할 수 있을까요?
마지막 글자를 처리하는 세 가지 방법이 있습니다. 한 글자를 다른 글자로 바꾸거나,
word1의 마지막 글자를 삭제하거나,word2의 마지막 글자를 삽입하는 것입니다. 각 방법은 더 짧은 접두사에 대해 동일한 문제를 남기므로, 가장 비용이 적게 드는 방법을 선택하고 1을 더하세요.모든 접두사 길이 쌍
(i, j)에 대한 답을 표에 저장합니다. 빈 접두사를 만들려면i번 삭제하거나j번 삽입해야 하므로 첫 번째 행과 열을 채울 수 있습니다. 나머지는 행별로 채우고 마지막 셀에서 답을 읽습니다.
풀이
편집은 서로 영향을 줍니다. garden과 ardent는 여섯 위치 모두에서 다르지만, 두 번의 편집이면 충분합니다. 따라서 각 단어의 마지막 글자를 살펴보세요. 두 글자가 같거나, 세 가지 편집 중 하나를 통해 같아질 수 있으며, 어느 쪽을 선택해도 더 짧은 접두사에 대한 같은 문제가 남습니다. 표를 사용하면 모든 접두사 쌍을 한 번씩 해결할 수 있습니다.
재귀를 사용하여 세 가지 편집을 모두 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
edits(i, j)를 접미사 word1[i:]를 word2[j:]로 바꾸는 데 필요한 최소 편집 횟수라고 하자. 첫 글자가 일치하면 그대로 두고 두 인덱스를 모두 이동한다. 일치하는 글자를 편집해도 도움이 되지 않기 때문이다. 그렇지 않으면 다음 세 가지 호출 중 비용이 가장 적은 것에 1을 더한다. 교체는 두 인덱스를 모두 이동하고, word1[i]를 삭제하면 i를 이동하며, word2[j]를 삽입하면 j를 이동한다. 한 단어가 먼저 끝나면 다른 단어에 남은 각 글자마다 편집 1회가 든다.
일치하지 않을 때마다 세 번의 호출이 시작된다. 공통 글자가 없는 15글자 단어 두 개에는 약 6.7 × 10^10회의 호출이 든다. 하지만 서로 다른 (i, j) 쌍은 (n+1) × (m+1)개뿐이므로, 거의 모든 호출은 이전 호출을 반복한다.
알고리즘
i가word1의 끝을 지났다면m - j를 반환하고,j가word2의 끝을 지났다면n - i를 반환합니다.word1[i] == word2[j]이면edits(i+1, j+1)을 반환합니다.- 그렇지 않으면
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1))을 반환합니다. - 정답은
edits(0, 0)입니다.
def minDistance(word1, word2):
n, m = len(word1), len(word2)
def edits(i, j):
# Fewest edits to turn word1[i:] into word2[j:]
if i == n:
return m - j # insert the rest of word2
if j == m:
return n - i # delete the rest of word1
if word1[i] == word2[j]:
return edits(i + 1, j + 1)
return 1 + min(edits(i + 1, j + 1), # replace word1[i] with word2[j]
edits(i + 1, j), # delete word1[i]
edits(i, j + 1)) # insert word2[j]
return edits(0, 0)접두사 표를 채우세요
핵심 아이디어
dp[i][j]를 word1의 처음 i개 문자를 word2의 처음 j개 문자로 바꾸는 데 필요한 최소 편집 횟수라고 하자. word1[i-1]가 word2[j-1]와 같으면 대각선의 dp[i-1][j-1] 값을 그대로 가져온다. 그렇지 않으면 가장 작은 이웃 값에 1을 더한다. 대각선은 교체, 위쪽 셀은 word1[i-1] 삭제, 왼쪽 셀은 word2[j-1] 삽입을 나타낸다. 기본 행과 열은 0이 아니다. i개의 문자를 아무것도 없는 상태로 바꾸려면 i번 삭제해야 하므로 dp[i][0] = i이고, 마찬가지로 dp[0][j] = j이다.
spot을 stop으로 바꿀 때 마지막 행은 [4, 3, 2, 2, 2]이다. 마지막 셀은 t와 p를 비교한다. 대각선 값(spo를 sto로 바꾸는 경우)은 1이고 다른 이웃 값은 2이므로, 답은 1 + 1 = 2이다. 길이가 500인 단어 두 개는 2.5 × 10^5개의 셀을 채우며, 각 셀은 상수 시간에 계산된다.
알고리즘
(n+1) × (m+1)개의 셀로dp를 만들고,dp[i][0] = i와dp[0][j] = j로 설정합니다.i를 1부터n까지,j를 1부터m까지 반복합니다.word1[i-1] == word2[j-1]이면dp[i][j] = dp[i-1][j-1]로 설정합니다.- 그렇지 않으면
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])로 설정합니다. dp[n][m]을 반환합니다.
def minDistance(word1, word2):
n, m = len(word1), len(word2)
# dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # delete all i letters
for j in range(m + 1):
dp[0][j] = j # insert all j letters
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete word1[i-1]
dp[i][j - 1]) # insert word2[j-1]
return dp[n][m]두 행만 유지하세요
핵심 아이디어
행 i는 행 i-1과 왼쪽에 있는 자신의 셀만 읽으므로 배열 두 개면 충분합니다. 완성된 행을 위한 prev와 채우고 있는 행을 위한 cur입니다. 대각선은 prev[j-1], 위쪽은 prev[j], 왼쪽은 cur[j-1]입니다. 이제 기본 열은 각 행의 첫 번째 항목에 있으므로 행 i를 채우기 전에 cur[0] = i로 설정하세요.
word2를 word1로 바꾸는 데 필요한 편집 횟수는 삽입과 삭제의 역할이 서로 바뀌므로 같습니다. 행이 더 짧은 단어를 따라가도록 단어의 순서를 바꾸세요. 그러면 최대 251,001개의 셀로 이루어진 표 대신 행마다 min(n, m) + 1개의 숫자만 사용하면서, 작업량은 동일하게 O(n × m)입니다.
알고리즘
word2가word1보다 길면 서로 바꾸세요.prev = [0, 1, ..., m]로 설정하세요.- 1부터
n까지 각i에 대해cur[0] = i로 설정하고, 표의 규칙에 따라cur[1..m]을 채우세요. 대각선과 위쪽 값은prev에서, 왼쪽 값은cur에서 읽으세요. 그런 다음prev와cur를 서로 바꾸세요. prev[m]을 반환하세요.
def minDistance(word1, word2):
if len(word2) > len(word1):
word1, word2 = word2, word1 # the rows run along the shorter word
m = len(word2)
# prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
prev = list(range(m + 1))
for i in range(1, len(word1) + 1):
cur = [i] + [0] * m # i letters into an empty prefix: delete them all
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete word1[i-1]
cur[j - 1]) # insert word2[j-1]
prev = cur
return prev[m]
함정과 경계 사례
- 가장 긴 공통 부분 수열에서처럼 행 0과 열 0을 0으로 채우는 것.
abc를 빈 접두사로 바꾸려면 삭제 3회가 필요하며, 0회가 아닙니다. - 두 행 버전에서
cur[0] = i를 빠뜨리는 것. 첫 번째 항목에는 두 행 이전의 값이 남고, 그 뒤의 모든 셀도 잘못된 값이 됩니다. - 일치하는 문자에 편집 비용을 부과하는 것. 같은 문자에 대해
1 + min(...)을 사용하면a를a로 바꾸는 데 비용이 1 듭니다. - 왼쪽 이웃을
cur대신prev에서 읽는 것. 왼쪽은 현재 행에서word2[j-1]를 삽입하는 경우입니다. - Python에서 길이 500인 단어에 메모이제이션된 재귀를 사용하는 것. 호출 깊이가 1000까지 올라가 기본 재귀 한도를 넘습니다.
자주 묻는 질문3
편집 거리의 시간 복잡도는 얼마인가요?
테이블을 사용하는 해법은 접두사 쌍마다 셀 하나를 채우므로, 길이가 n과 m일 때 시간은 O(n × m)입니다. 전체 테이블을 사용하면 메모리는 O(n × m)이고, 두 행만 사용하면 O(min(n, m))입니다. 테이블을 사용하지 않는 단순 재귀는 지수 시간입니다.
편집 거리는 레벤슈타인 거리와 같은가요?
이 버전은 레벤슈타인 거리입니다. 삽입, 삭제, 교체의 비용은 각각 1입니다. 편집 거리는 이 개념의 통칭입니다. 삽입과 삭제만 허용하면 n + m - 2 × LCS가 되고, 길이가 같을 때 교체만 허용하면 해밍 거리가 되며, 서로 이웃한 두 글자의 교환을 추가하면 다메라우 버전이 됩니다.
편집 거리는 하나의 배열로 해결할 수 있을까요?
네. 하나의 배열 row을 왼쪽에서 오른쪽으로 제자리에서 채우세요. row[j]을 덮어쓰기 전에는 여전히 바로 위 행의 값이 들어 있고, row[j-1]에는 이미 현재 행의 값이 들어 있습니다. 대각선 값만 사라지므로, 이전 row[j] 값을 변수에 저장하고 j + 1의 대각선 값으로 사용하세요.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def minDistance(word1, word2):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
word1 = "spot" word2 = "stop"
예상 출력
2