최소한의 수정 횟수로 한 문자열을 다른 문자열로 변환하는 방법은 무엇입니까?

Question

전화 인터뷰에서이 질문을 받았습니다.

하나의 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 수를 두 문자열에서 찾습니다. 솔루션은 java로 구현되고 O (n * m)에서 실행되어야합니다. n과 m은 입력 문자열의 길이입니다.

예 :
문자열 : 우유 ->맥주
분 편집 : 서로 다른 길이의 문자열에 대한 4

Answer 1

, 사용 Levenshtein 거리 : http://en.wikipedia.org/wiki/Levenshtein_distance

길이가 같은 문자열이 있고 삽입 또는 삭제를 고려하지 않으려는 경우 Ha mming 거리가 더 효율적입니다 : Levenshtein 거리의 http://en.wikipedia.org/wiki/Hamming_distance

예 구현 : http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

Answer 2

가정 : 말씀은 별개의 문자가 포함되어 있습니다.

S1 용 문자 해시를 만드는 방법은 어떻습니까?

이제 S2의 각 문자를 반복하고 S1의 Hashset에서 제거하려고합니다. 캐릭터를 제거 할 수 있으면 카운터를 증가시키지 마십시오. 그렇지 않으면 카운터를 증가시킵니다.

카운터에 최소 편집 횟수가 포함되어 있습니다.