超絶Pythonクイズ

問題

"全角"を含む文字列間の距離を表すレーベンシュタインの編集距離を求めるパフォーマンスの良い関数を書け

ただし、追加,削除,置換のコストをすべて1とする。

リーベンシュタインの編集距離とは？

レーベンシュタイン距離（レーベンシュタインきょり）あるいは編集距離（へんしゅうきょり）は、情報理論において、二つの文字列がどの程度異なっているかを示す数値である。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。
実際的な距離の求め方を例示すれば、“kitten”を“sitting”に変形する場合には、以下に示すように最低でも 3 回の手順が必要とされるので、2単語間のレーベンシュタイン距離は 3 となる。
kitten
sitten （“k”を“s”に置換）
sittin （“e”を“i”に置換）
sitting （“g”を挿入して終了）
(wikipediaより)

ヒント(半角文字列の場合の編集距離を求める関数)

def levenshtein(s1, s2):
    if len(s1) < len(s2):
        return levenshtein(s2, s1)

    # len(s1) >= len(s2)
    if len(s2) == 0:
        return len(s1)

    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
            deletions = current_row[j] + 1       # than s2
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row

    return previous_row[-1]

下記より引用
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python