← 20주차 · DP 심화 (2차원)
어려움DP문자열

편집 거리

두 문자열 a와 b가 주어져요. a를 b로 바꾸는 데 필요한 최소 편집 횟수를 반환해요. 한 번의 편집은 글자 하나를 삽입, 삭제, 또는 교체하는 것이에요.

dp[i][j]를 'a의 앞 i글자를 b의 앞 j글자로 바꾸는 최소 횟수'라 해요. 마지막 글자가 같으면 그대로 dp[i-1][j-1]이고, 다르면 삭제·삽입·교체 세 방향(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 중 가장 작은 값에 1을 더해요.

빈 문자열로 시작하는 경계도 중요해요. a의 i글자를 빈 문자열로 만들려면 i번 삭제, 빈 문자열을 b의 j글자로 만들려면 j번 삽입이 필요해요.

예시

예시 1
입력
a = "horse", b = "ros"
출력
3
설명
horse → rorse(교체) → rose(삭제) → ros(삭제), 세 번이에요.
예시 2
입력
a = "intention", b = "execution"
출력
5

제한 사항

  • 0 ≤ a.length, b.length ≤ 1,000
  • 두 문자열은 소문자 알파벳으로 이루어져요.
(a.length + 1) × (b.length + 1) 표를 만들고 첫 행·첫 열을 0, 1, 2… 로 채워요(빈 문자열과의 거리). 나머지는 글자가 같으면 왼쪽 위 대각선 값을 그대로, 다르면 위·왼쪽·대각선 세 값의 최솟값에 1을 더해 채워요.
javascript
function editDistance(a, b) {
  const m = a.length;
  const n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  return dp[m][n];
}
이전 문제최장 공통 부분 수열
다음 문제다익스트라 최단 경로
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.