문자열의 편집 거리

문자열의 편집 거리

빌드업 1

문자열에는 다음과 같이 네가지 작용이 있다:

  1. 삽입: 문자열에 새로운 문자를 끼워넣는다.
  2. 제거: 문자열에서 문자 하나를 없앤다.
  3. 교체: 문자열에서 문자 하나를 다른 문자로 바꾼다.
  4. 전치: 두 문자의 위치를 서로 바꾼다.

정의

편집 거리는 문자열간의 거리 함수로써 편집 방법을 허용하거나 금지함으로써 다음과 같은 타입들로 구분된다:


  1. https://en.wikipedia.org/wiki/Edit_distance ↩︎

댓글