계산 편집 거리로 Levenshtein

Question

문제 : 나에게 제대로 작동하려면 나타납니다,하지만 분명히 잘못된 답을 낳는 Levenshtein 문자열 편집 프로그램을 코딩 한
. 나는 편집 거리가 계산되는 방법을 오해한다고 생각합니다.

a n t i g r a v i t a t i o n a l 
c 6 6 6 6 6 6 6 6 7 8 9 10 11 12 13 14 15 16 
a 7 6 7 7 7 7 7 6 7 8 9 9 10 11 12 13 13 14 

기타 :

,691,363 문자열 superca 및 antigravitational에 대한

비교
, 여기

내 마지막 두 행의 비교입니다 내 계산에

a n t i g r a v i t a t i o n a l c 6 6 6 6 6 6 6 6 7 8 9 10 11 12 13 14 15 16 a 7 6 7 7 7 7 7 6 7 8 9 9 10 11 12 13 14 15 

(210)는, 그 마지막이 "a"는 antigravitational에 "는"이 superca에 그래서 난 왼쪽이를 직접적에 수 있기 때문에 그것을 (13)의 값을 준 일치하기 때문에 볼 수 있습니다 따라서 비용은 0입니다.

다른 계산에서 사람들은 여전히 ​​이러한 상황에서 비용을 추가하는 것처럼 보입니다. 다른 예제에서 볼 수 있듯이, 그들은 14를 배치했는데 13을 놓으면 최종 편집 거리는 15가되었습니다 (14와 반대).

내가 맞고 다른 모든 사람들이 잘못 되었나요? 아니면 단계가 빠졌습니까?

Answer 1

YouTube 동영상 몇 개를 읽은 후 내 답변을 찾았습니다.

내 실수는
내 지침은 일치를 비교하는 문자는 0으로 비용을 설정하면 "명시된 최소 (왼쪽 대각선 위)가 일치하지 않는 경우. 추가 복사 1.

보정
그래서 지침이 약간 부정확했다. 문자에 관계없이 왼쪽 값과 값이 위의 무엇인지, 당신은 항상 무료로 대각선을 복사해야합니다 일치하는 경우에.