최소 작업 횟수

Question

문제가 있습니다. 주어진 문자열이 있다고 가정합니다. "최고", 대상 문자열은 "짐승"입니다. 주어진 문자열을 대상 문자열로 변환하는 연산의 수를 결정해야하지만 허용되는 연산은 다음과 같습니다. 1. 문자열에 문자를 추가합니다. 2. 문자를 삭제하십시오. 3. 두 문자 위치를 바꿉니다. (현명하게 사용하면 교환 할 수있는 기회는 하나뿐입니다.)

위의 경우 1입니다. 어떻게 이런 종류의 문제를 해결하고 어떤 종류의 문제입니까? 나는 초보자입니다. 이런 종류의

Answer 1

Levenshtein distance

Answer 2

한 널리 사용되는 측정은 Levenshtein 거리라고합니다.

http://en.wikipedia.org/wiki/Levenshtein_distance

는 WP 페이지는 또한 다른 유사한 개념/링크를 언급하고있다. 이것은 본질적으로 한 단어를 다른 단어로 변환하는 데 필요한 편집 수의 척도입니다.