최소 편집 거리 2

두 문자열 X와 Y가 주어진다. 문자열 X에 다음 네 가지 편집 연산을 사용해 X를 Y와 같게 만들려고 한다. 한 번의 연산은 아래 중 하나이다.

1. 삽입: X의 원하는 위치에 알파벳 소문자 하나를 삽입한다.
2. 삭제: X에서 원하는 문자 하나를 삭제한다.
3. 대체: X에서 원하는 문자 하나를 다른 알파벳 소문자로 바꾼다.
4. 교환: X에서 서로 인접한 두 문자의 위치를 서로 바꾼다.

X를 Y로 바꾸는 데 필요한 최소 편집 횟수를 구하시오.

첫째 줄에 문자열 X, 둘째 줄에 문자열 Y가 주어진다. 두 문자열의 길이는 각각 1 이상 1,000 이하이며, 알파벳 소문자로만 이루어져 있다.

X를 Y로 바꾸는 데 필요한 최소 편집 횟수를 출력한다.