Edit Distance

Q: 편집 거리의 시간 복잡도는 얼마인가요?

테이블 방식의 해법은 두 길이인 n 과 m 에 대해 O(n × m) 시간으로 실행됩니다. 각 접두사 쌍마다 일정한 작업으로 셀 하나를 채우기 때문입니다. 전체 테이블을 사용하면 O(n × m) 메모리를 사용하고, 두 행만 사용하면 O(min(n, m)) 메모리를 사용합니다. 테이블 없이 단순 재귀를 사용하면 지수 시간이 걸립니다.

Q: 편집 개수뿐만 아니라 편집 목록은 어떻게 가져오나요?

전체 표를 유지하고 dp[n][m] 에서 거슬러 올라가세요. 문자가 일치하면 편집 없이 대각선으로 이동하세요. 일치하지 않으면 값이 1만큼 작은 이웃 칸으로 이동하세요. 대각선은 교체, 위쪽은 삭제, 왼쪽은 삽입입니다. dp[0][0] 에 도달할 때까지 이동한 다음 편집을 역순으로 읽으세요. 두 행 버전은 이전 행들을 버렸기 때문에 이것만으로는 할 수 없습니다.

Q: 편집 거리를 배열 하나만으로 구할 수 있을까요?

네. 배열 row 하나를 제자리에서 왼쪽에서 오른쪽으로 채웁니다. row[j] 를 덮어쓰기 전에는 여전히 위쪽 행의 값이 들어 있고, row[j-1] 에는 이미 현재 행의 값이 들어 있습니다. 잃게 되는 유일한 값은 대각선 값이므로 변수에 저장해 두세요. 쓰기 전에 기존 row[j] 를 저장하고, 이를 j + 1 의 대각선 값으로 사용합니다.

어려움동적 계획법

+10

두 단어 word1과 word2가 주어집니다. 한 번의 편집으로 word1을 세 가지 방법 중 하나로 변경할 수 있습니다. 즉, 아무 위치에나 글자를 삽입하거나, 글자를 삭제하거나, 글자를 다른 글자로 바꿀 수 있습니다. word1을 word2로 바꾸는 데 필요한 최소 편집 횟수를 반환하세요.

함수

minDistance(word1: string, word2: string) → integer

word1string: 네가 편집하는 단어
word2string: 도달해야 할 단어
반환값integer: word1을 word2로 바꾸는 데 필요한 삽입, 삭제 및 대체의 최소 횟수

제약 조건

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
두 단어 모두 소문자 영어 문자만 포함합니다.

예제

입력: word1 = "spot"word2 = "stop"
출력: 2
설명: p를 t로, t를 p로 바꾸세요. spot은 stot이 되고, 그다음 stop이 됩니다. 단어가 두 곳에서 다르고 삽입이나 삭제를 하면 길이가 달라지므로 한 번의 편집으로는 충분하지 않습니다.

입력: word1 = "garden"word2 = "ardent"
출력: 2
설명: g를 삭제하면 arden이 되고, 그다음 끝에 t를 삽입하면 ardent가 됩니다. 글자를 하나씩 바꾸면 두 단어가 모든 위치에서 다르므로 비용이 6입니다.

입력: word1 = "rain"word2 = "shine"
출력: 3
설명: r을 s로 바꾸고 a를 h로 바꾸면 shin이 되고, 그다음 e를 삽입합니다. 두 번의 편집으로는 할 수 없습니다. r과 a는 shine에 나타나지 않으므로, 각각 단어를 더 길게 만들지 않는 편집이 필요하며, 단어는 여전히 한 글자 늘어나야 합니다.

제출 시 숨은 테스트 +21개

후속 질문

편집 횟수뿐 아니라, 가장 짧은 편집 목록 하나도 반환해 줄 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

편집은 서로 영향을 주므로 단어를 위치별로 고칠 수 없습니다. garden과 ardent는 여섯 위치 모두에서 다르지만, g를 삭제하고 나면 모든 것이 왼쪽으로 이동하므로 편집 두 번이면 충분합니다. 이를 해결하는 핵심 아이디어는 각 단어의 마지막 글자만 살펴보는 것입니다. 두 글자가 이미 같거나, 정확히 세 가지 편집 중 하나를 적용해 같게 만들 수 있으며, 어느 선택을 하든 더 짧은 접두사에 대해 같은 문제가 남습니다. (n+1) × (m+1)개의 답을 담은 표를 사용하면 모든 접두사 쌍을 한 번씩 해결할 수 있고, 그중 두 행이면 충분합니다.

재귀를 사용해 세 가지 편집을 모두 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

edits(i, j)를 접미사 word1[i:]를 word2[j:]로 바꾸는 데 필요한 최소 편집 횟수라고 하자. 두 접미사의 첫 글자를 살펴보자. 두 글자가 같으면 그대로 두고 두 인덱스를 모두 다음으로 이동한다. 일치하는 글자는 편집할 필요가 없으며, 그 글자를 편집하는 계획은 길이를 늘리지 않고 그대로 두는 계획으로 바꿀 수 있다.

두 글자가 다르면 word1[i]를 처리하거나 word2[j]를 만들어 내기 위해 편집이 필요하며, 방법은 정확히 세 가지다. word1[i]를 word2[j]로 바꾸고 두 인덱스를 모두 다음으로 이동한다: edits(i+1, j+1). word1[i]를 삭제하고 i만 이동한다: edits(i+1, j). word1[i] 앞에 word2[j]를 삽입하고 j만 이동한다: edits(i, j+1). 답은 1에 세 방법 중 가장 적은 비용을 더한 값이다. word1이 끝나면 word2의 나머지를 삽입하며, 비용은 m - j다. word2가 끝나면 word1의 나머지를 삭제하며, 비용은 n - i다.

불일치가 발생할 때마다 호출을 세 번 하기 때문에 느리다. 공통된 글자가 없는 15글자 단어 두 개의 경우 호출은 약 6.7 × 10^10번이며, 큰 테스트에는 각각 500글자씩 있다. 하지만 서로 다른 쌍 (i, j)는 (n+1) × (m+1)개뿐이므로, 거의 모든 호출은 이전에 했던 호출을 반복한다.

알고리즘

i와 j에서 시작하는 접미사에 대해 edits(i, j)를 작성합니다.
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개 문자로 바꾸는 데 필요한 최소 편집 횟수라고 하자. 인덱스 0은 빈 접두사를 나타낸다.

전이. 두 접두사의 마지막 문자 word1[i-1]와 word2[j-1]를 비교한다. 서로 같으면 그대로 둔다. 즉, 대각선 왼쪽 위 셀인 dp[i][j] = dp[i-1][j-1]이다. 다르면 편집을 한 번 하고 세 이웃 셀 중 가장 작은 값을 선택한다. 대각선 셀 dp[i-1][j-1]은 word1[i-1]을 word2[j-1]로 바꾸는 것을 의미한다. 위쪽 셀 dp[i-1][j]는 word1[i-1]을 삭제하는 것을 의미한다. 왼쪽 셀 dp[i][j-1]은 끝에 word2[j-1]을 삽입하는 것을 의미한다.

기본 행과 열. 많은 표 문제와 달리 기본 행과 열의 값은 0이 아니다. i개 문자를 빈 접두사로 바꾸려면 i번 삭제해야 하므로 dp[i][0] = i이다. 아무것도 없는 상태에서 j개 문자를 만들려면 j번 삽입해야 하므로 dp[0][j] = j이다. 각 셀은 위쪽 셀, 왼쪽 셀, 대각선 셀을 참조하므로 행마다 왼쪽에서 오른쪽으로 채우면 필요한 값이 이미 계산되어 있다. 정답은 dp[n][m]이다.

spot을 stop으로 바꾸는 표는 다음과 같다. 열은 접두사 "", s, st, sto, stop에 해당한다. 행 ""는 [0, 1, 2, 3, 4], 행 s는 [1, 0, 1, 2, 3], 행 sp는 [2, 1, 1, 2, 2], 행 spo는 [3, 2, 2, 1, 2], 행 spot은 [4, 3, 2, 2, 2]이다. 몇 개의 셀을 살펴보자. s와 s는 일치하므로 대각선 값 0을 그대로 가져온다. sp와 st는 일치하지 않는다. 이 셀의 이웃 값은 대각선이 0, 위쪽이 1, 왼쪽이 1이므로 1 + 0 = 1이다. 즉, 한 번 바꾸면 된다. spo와 sto는 o가 일치하므로 값 1을 그대로 가져온다. 마지막 셀에서는 spot과 stop을 비교하며, 이때 마지막 문자는 각각 t와 p이다. 이 셀의 이웃 값은 1, 2, 2이므로 정답은 1 + 1 = 2이다.

표에는 (n+1) × (m+1)개의 셀이 있고 각 셀을 계산하는 데 상수 시간이 걸린다. 따라서 길이가 500자인 두 단어의 경우 약 2.5 × 10^5 단계가 필요하다. 메모이제이션을 사용하는 재귀도 같은 셀을 채우지만, 재귀 깊이가 최대 n + m번의 호출에 이를 수 있으며, 이는 Python의 기본 제한인 1000을 넘는다.

알고리즘

(n+1) × (m+1)개의 셀로 이루어진 dp 테이블을 만듭니다.
모든 i에 대해 dp[i][0] = i로 설정하고, 모든 j에 대해 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로 설정하세요. 행 0은 기본 행인 [0, 1, 2, ..., m]으로 시작합니다.

word2를 word1로 바꾸는 데 필요한 편집 횟수는 동일합니다. 삽입은 삭제가 되고 삭제는 삽입이 되기 때문입니다. 따라서 두 단어의 순서를 바꿔 행이 더 짧은 단어를 따라가게 할 수 있습니다. 그러면 각 행은 최대 251,001개의 셀로 이루어진 표 대신 min(n, m) + 1개의 숫자만 담으며, 작업량은 계속 O(n × m)입니다.

알고리즘

word2가 word1보다 길면 서로 바꾸세요.
prev = [0, 1, ..., m]으로 설정하세요. 여기서 m은 더 짧은 길이입니다.
1부터 n까지 각 i에 대해 cur[0] = i로 설정한 다음, prev에서 대각선과 위쪽 값을, cur에서 왼쪽 값을 읽어 같은 규칙으로 cur[1..m]을 채우세요.
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회가 아니므로, dp[i][0]은 i여야 하고 dp[0][j]는 j여야 합니다.
두 행 버전에서 cur[0] = i를 빠뜨리는 경우. 첫 번째 항목에 두 행 전의 값이 남고, 그 뒤의 모든 셀 값이 잘못됩니다.
문자가 일치할 때 편집 비용을 더하는 경우. 문자가 같을 때 dp[i][j] = 1 + min(...)을 사용하면 a를 a로 바꾸는 데 비용이 1이 듭니다. 일치할 때는 대각선 값을 복사하세요.
왼쪽 이웃을 cur 대신 prev에서 읽는 경우. 왼쪽은 현재 행입니다. word1[:i]가 이미 word2[:j-1]로 바뀐 뒤 word2[j-1]을 삽입하는 경우에 해당합니다.
위치를 하나씩 비교하는 경우. 단어에서 서로 다른 위치의 개수를 세면 삽입과 삭제를 무시하게 됩니다. 그래서 garden과 ardent의 결과는 6이지만, 정답은 2입니다.
500글자 단어에 재귀를 사용해 메모이제이션하는 경우. 호출 깊이가 1000에 이르는데, 이는 Python의 기본 한도입니다.

자주 묻는 질문4

편집 거리의 시간 복잡도는 얼마인가요?

테이블 방식의 해법은 두 길이인 n과 m에 대해 O(n × m) 시간으로 실행됩니다. 각 접두사 쌍마다 일정한 작업으로 셀 하나를 채우기 때문입니다. 전체 테이블을 사용하면 O(n × m) 메모리를 사용하고, 두 행만 사용하면 O(min(n, m)) 메모리를 사용합니다. 테이블 없이 단순 재귀를 사용하면 지수 시간이 걸립니다.

편집 거리는 레벤슈타인 거리와 같은가요?

네, 이 버전은 레벤슈타인 거리입니다. 삽입, 삭제, 치환의 비용은 각각 1입니다. 편집 거리는 이 계열의 이름입니다. 다른 종류는 허용하는 편집 연산이 더 적거나 많습니다. 삽입과 삭제만 허용하면 n + m - 2 × LCS가 되고, 길이가 같은 문자열에서 치환만 허용하면 해밍 거리가 되며, 인접한 두 문자를 맞바꾸는 연산을 추가하면 다메라우 버전이 됩니다.

편집 개수뿐만 아니라 편집 목록은 어떻게 가져오나요?

전체 표를 유지하고 dp[n][m]에서 거슬러 올라가세요. 문자가 일치하면 편집 없이 대각선으로 이동하세요. 일치하지 않으면 값이 1만큼 작은 이웃 칸으로 이동하세요. 대각선은 교체, 위쪽은 삭제, 왼쪽은 삽입입니다. dp[0][0]에 도달할 때까지 이동한 다음 편집을 역순으로 읽으세요. 두 행 버전은 이전 행들을 버렸기 때문에 이것만으로는 할 수 없습니다.

편집 거리를 배열 하나만으로 구할 수 있을까요?

네. 배열 row 하나를 제자리에서 왼쪽에서 오른쪽으로 채웁니다. row[j]를 덮어쓰기 전에는 여전히 위쪽 행의 값이 들어 있고, row[j-1]에는 이미 현재 행의 값이 들어 있습니다. 잃게 되는 유일한 값은 대각선 값이므로 변수에 저장해 두세요. 쓰기 전에 기존 row[j]를 저장하고, 이를 j + 1의 대각선 값으로 사용합니다.

Python

def minDistance(word1, word2):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

word1 = "spot"
word2 = "stop"

기대값

Edit Distance

함수

제약 조건

예제

힌트

풀이

재귀를 사용해 세 가지 편집을 모두 시도해 보세요

접두사 표 채우기

두 행만 유지

함정과 경계 사례

자주 묻는 질문4

비슷한 문제