문자열을 다른 것으로 바꾸는 데 걸리는 변경 횟수

Question

문자열을 s1에서 s2로 변경하는 데 필요한 변경 횟수를 알아 내려고합니다. 내가 정확히 할 함수를 썼다지만 내가 처음으로 두 문자 다를 경우 그것은 1을 반환하고 문자열의 나머지 부분을 보지 않는다면 내가 지금까지 가지고있는 문제가 있습니다.

는 여기에 지금까지이 작업은 다음과 같습니다

def num_of_changes(s1, s2): 
    if not s1: 
     return len(s2) 
    if not s2: 
     return len(s1) 
    length = 0 
    # if the first char in both the string are the same, then call the function 
    # again on the rest of the string after the first char. 
    # so if s1 = cat and s2 = cbt since the first char on both strings is 
    # the same it call the function again on the rest, the rest in this case 
    # being s1 = at and s2 = bt 
    if s1[0] == s2[0]: 
     num_of_changes(s1[length+1:], s2[length+1:]) 
    # if the first characters on both the strings aren't the same, then 
    # increase the length by 1, and call the function again on the rest of the 
    # string after length + 1. 
    # so if s1 = cat and s2 = bat, since the first char from both the strings 
    # arent the same it calls the function on length+1. Since the length 
    # increased to 1 becase the first char isn't the same, the it would be 
    # length=1, so 1+1 
    # Therefore, it would call the function on s1 = at and s2 = at 
    else: 
     length += 1 
     num_of_changes(s1[length+1:], s2[length+1:]) 
    # returns the number stored in the length variable. 
    return length 

Answer 1

당신은 재귀 호출의 반환 값을 무시하고 있습니다. 그들은 길이를 반환하지만 그 값은 바닥에 떨어집니다. 우리는 이러한 재귀 호출을 제거하면, 다음 코드는 동일합니다 : 당신은, 그것은 단지 당신은 재귀 값을 얻을 필요가 0 또는 1

돌아갑니다 볼 수 있듯이

length = 0 
if s1[0] == s2[0]: 
    pass 
else: 
    length += 1 
return length 

다음 조건에 추가 첫 번째 문자가 일치하면 1입니다. 1에 length+1 변경, 두 개의 리턴 문을 병합하여

if s1[0] == s2[0]: 
    return num_of_changes(s1[length+1:], s2[length+1:]) 
else: 
    return num_of_changes(s1[length+1:], s2[length+1:]) + 1 

는, 이것이 다음에 간단하게 할 수있다 :

return num_of_changes(s1[1:], s2[1:]) + (1 if s1[0] == s2[0] else 0) 

그것은 약간의 밀도가 될 수 있지만 그것은 분명 무엇을하게 당신 ' 재귀 호출 : 재귀 호출의 값에 s1[0] == s2[0] 인 경우 1을 더한 값입니다.

Answer 2

찾고있는 기능을 두 행간 편집 거리 또는 Levenshtein 거리라고합니다. python-Levenshtein 패키지에 구현되어 있습니다. 을 통해 설치 :

$ sudo pip install python-Levenshtein 

그리고 다음과 같이 사용 :

>>> import Levenshtein 
>>> Levenshtein.distance('abba', 'baba') 
2