編集距離 (レーベンシュタイン距離)
(DP/levenshtein_distance.py)

• View this file on GitHub
• Last update: 2021-05-05 22:42:50+09:00

概要

文字列 $S$ を $T$ へと変換するときの最小の操作回数を求めるアルゴリズム。操作には以下の方法がある。

• 変更操作: $S$ から文字を $1$ 個選び、変更する。
• 削除操作: $S$ から文字を $1$ 個選び、削除する。
• 挿入操作: $S$ の好きな箇所に文字を $1$ 個挿入する。

使い方

levenshtein_distance(s: str, t: str) -> int
長さ $N$ の文字列 s を 長さ $M$ の文字列 t に変換するときの最小操作回数を返す。計算量 $O(NM)$

Verified with

• TestCase/yukicoder/yuki0225.test.py

Code

def levenshtein_distance(s, t):
    len_s = len(s)
    len_t = len(t)
    INF = 10 ** 18
    dp = [[INF] * (len_t + 1) for _ in range(len_s + 1)]
    for i in range(len_s + 1):
        dp[i][0] = i
    for j in range(len_t + 1):
        dp[0][j] = j

    for i in range(len_s):
        for j in range(len_t):
            # 変更操作
            if s[i] == t[j]:
                dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j])
            else:
                dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1)
            # 削除操作
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j + 1] + 1)
            # 挿入操作
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i + 1][j] + 1)

    return dp[len_s][len_t]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page