將字符串轉換爲另一個字符所需的更改次數

Question

我試圖找出將第一個字符串s1更改爲所需的更改次數。我寫了一個函數來做到這一點 ，但到目前爲止，我的問題是，如果前兩個字符 不同，那麼它會返回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

你忽略從遞歸調用的返回值。他們返回一個長度，但這些值被放在地板上。如果我們消除這些遞歸調用，那麼，你的代碼就相當於：

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

正如你所看到的，它只會返回0或1。

你需要得到遞歸值，然後添加有條件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 

通過改變length+1到1，和合並兩個return語句，這然後可以簡化爲：

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

這可能有點密集，但是這使得它非常清楚你」重新返回：這是遞歸調用的值，加上1如果s1[0] == s2[0]。

Answer 2

您正在查找的函數稱爲兩個字符串之間的編輯距離或Levenshtein距離。你可以在python-Levenshtein包中找到它。通過安裝：

$ sudo pip install python-Levenshtein 

而且使用這樣的：

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