편집 거리

한 문자열을 다른 문자열로 바꾸는 데 필요한 삽입·삭제·교체 연산의 최소 횟수를 구하는 문제입니다. 레벤슈타인 거리(Levenshtein distance)라고도 합니다.

동작 과정

dp[i][j] = A의 앞 i글자를 B의 앞 j글자로 바꾸는 최소 연산 수.

A = "sunday", B = "saturday"

        ""  s  a  t  u  r  d  a  y
    "" [ 0  1  2  3  4  5  6  7  8 ]
    s  [ 1  0  1  2  3  4  5  6  7 ]
    u  [ 2  1  1  2  2  3  4  5  6 ]
    n  [ 3  2  2  2  3  3  4  5  6 ]
    d  [ 4  3  3  3  3  4  3  4  5 ]
    a  [ 5  4  3  4  4  4  4  3  4 ]
    y  [ 6  5  4  4  5  5  5  4  3 ]
                                  ↑ 답 = 3

첫 행/열은 "빈 문자열로 만들기" = 전부 삭제/삽입
  dp[i][0] = i,  dp[0][j] = j

칸을 채우는 규칙:
  A[i] == B[j] → dp[i][j] = dp[i-1][j-1]              (그대로 두기, 비용 0)
  A[i] != B[j] → dp[i][j] = 1 + min(
                     dp[i-1][j-1],   교체
                     dp[i][j-1],     삽입
                     dp[i-1][j])     삭제

예: i=3(n), j=3(t) → 불일치
    1 + min(dp[2][2]=1, dp[3][2]=2, dp[2][3]=2) = 1 + 1 = 2

sunday → saturday의 실제 연산 3개: a 삽입, t 삽입, n→r 교체.

구현

int editDistance(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 0; i <= n; i++) dp[i][0] = i;   // 전부 삭제
    for (int j = 0; j <= m; j++) dp[0][j] = j;   // 전부 삽입

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],              // 교체
                                Math.min(dp[i][j - 1], dp[i - 1][j])); // 삽입, 삭제
            }
        }
    }
    return dp[n][m];
}

// 공간 O(M) — 직전 행만 필요하다
int editDistanceOptimized(String a, String b) {
    int m = b.length();
    int[] prev = new int[m + 1];
    int[] cur = new int[m + 1];

    for (int j = 0; j <= m; j++) prev[j] = j;

    for (int i = 1; i <= a.length(); i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                cur[j] = prev[j - 1];
            } else {
                cur[j] = 1 + Math.min(prev[j - 1], Math.min(cur[j - 1], prev[j]));
            }
        }
        int[] tmp = prev; prev = cur; cur = tmp;   // 두 행을 번갈아 재사용
    }
    return prev[m];
}

복잡도

주의사항

• 첫 행/열 초기화: dp[i][0] = i, dp[0][j] = j를 빼먹고 0으로 두면 삭제·삽입 비용이 사라져 답이 작아진다
• 세 방향의 의미 혼동: 대각선=교체, 왼쪽=삽입, 위=삭제. 어느 쪽이 삽입인지는 "i를 고정하고 j를 늘렸다 = B에 글자를 맞춰 넣었다"로 따지면 헷갈리지 않는다
• 연산 비용이 다른 변형: 삽입/삭제/교체 비용이 1이 아닌 문제라면 1 + 자리를 각 비용으로 바꾼다. 교체를 금지하는 변형은 대각선 전이를 제거하면 되고, 그 경우 답은 LCS로 계산할 수 있다
• 공간 최적화 시 복원 불가: 두 행만 유지하면 어떤 연산을 했는지 역추적할 수 없다

핵심 정리

• 삽입·삭제·교체로 두 문자열을 같게 만드는 최소 연산 수
• 일치하면 대각선 그대로, 불일치하면 세 방향의 최솟값 + 1
• 시간 O(NM), 공간은 두 행만 유지해 O(min(N,M))까지 줄일 수 있다
• 교체를 금지한 변형은 LCS 문제로 환원된다

→ 동적 계획법