두 문구를 맞추는 최소 수정 횟수

자바스크립트 코딩테스트 문제로 edit-distance 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium edit-distance 함수명: minimumMessageEditCount 제한 시간: 500ms

두 문구를 같게 만들기 위해 필요한 최소 수정 횟수를 구하세요.

문제 설명

문자열 source와 target이 주어집니다.

한 번의 수정으로 다음 연산 중 하나를 수행할 수 있습니다.

문자 하나를 삽입합니다.
문자 하나를 삭제합니다.
문자 하나를 다른 문자로 교체합니다.

source를 target과 같게 만드는 데 필요한 최소 수정 횟수를 반환하는 minimumMessageEditCount 함수를 작성하세요.

제한사항

0 <= source.length, target.length <= 2,000
두 문자열은 영문 소문자로만 이루어져 있습니다.
빈 문자열이 입력될 수 있습니다.
삽입, 삭제, 교체는 각각 수정 횟수 1로 계산합니다.

예시

입력: source = "cat", target = "cut" -> 출력: 1
- a를 u로 한 번 교체합니다.
입력: source = "kitten", target = "sitting" -> 출력: 3
입력: source = "abc", target = "" -> 출력: 3
입력: source = "same", target = "same" -> 출력: 0

힌트

dp[i][j]를 source의 앞 i글자를 target의 앞 j글자로 바꾸는 최소 수정 횟수라고 생각해 보세요.
마지막 문자가 같으면 이전 접두사의 정답을 그대로 사용할 수 있습니다.
마지막 문자가 다르면 삽입, 삭제, 교체 중 가장 적은 비용을 선택합니다.

해설

문자열 전체를 한 번에 비교하기보다 두 문자열의 접두사 문제부터 해결하면 더 긴 문자열의 정답을 만들 수 있습니다.

source의 앞 i글자와 target의 앞 j글자를 비교한다고 합시다. 마지막 문자가 같다면 새 수정이 필요 없으므로 dp[i - 1][j - 1]을 그대로 사용합니다. 마지막 문자가 다르면 다음 세 경우 중 최솟값에 1을 더합니다.

삽입: dp[i][j - 1]
삭제: dp[i - 1][j]
교체: dp[i - 1][j - 1]

한쪽 접두사가 비어 있다면 다른 쪽의 모든 문자를 삽입하거나 삭제해야 합니다. 따라서 dp[0][j] = j, dp[i][0] = i로 초기화합니다.

현재 상태는 직전 행과 현재 행의 값만 참조합니다. 전체 2차원 배열을 저장하지 않고 두 행만 번갈아 사용하면 공간 복잡도를 O(target.length)로 줄일 수 있습니다. 두 문자열 중 짧은 쪽을 열로 두면 공간 사용량은 O(min(source.length, target.length))가 됩니다.

시간 복잡도는 O(source.length * target.length), 공간 복잡도는 O(min(source.length, target.length))입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과