擅长:python、mysql、java
<p>诀窍是生成所有长度适当的<code>b</code>的子串,然后对每个子串进行比较。在</p>
<pre><code>def lev_dist(a,b):
length_cost = abs(len(a) - len(b))
diff_cost = sum(1 for (aa, bb) in zip(a,b) if aa != bb)
return diff_cost + length_cost
def all_substr_of_length(n, s):
if n > len(s):
return [s]
else:
return [s[i:i+n] for i in range(0, len(s)-n+1)]
def lev_substr(a, b):
"""Gives minimum lev distance of all substrings of b and
the single string a.
"""
return min(lev_dist(a, bb) for bb in all_substr_of_length(len(a), b))
if lev_substr(str1, str2) < 2:
# it works!
</code></pre>