편집 거리

두 문자열 A, B가 주어질 때 A를 B로 바꾸는 데 필요한 최소 편집 횟수를 구하라. 이를 편집 거리(Levenshtein distance)라 한다.

사용할 수 있는 연산은 다음 세 가지이며, 각 연산의 비용은 1이다.

• 삽입: 임의의 위치에 문자 1개를 추가한다.
• 삭제: 임의의 위치의 문자 1개를 제거한다.
• 교체: 임의의 위치의 문자 1개를 다른 문자로 바꾼다.