0Pricing
Competitive Programming Academy · レッスン

編集距離を段階的に学ぶ

挿入、削除、置換で変換します

「編集距離を段階的に学ぶ」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

編集距離が測るもの

編集距離とは、ある文字列を別の文字列に変えるために必要な、1文字単位の編集回数の最小値です。2つの単語が実際にどれほど異なるかを表します。

3つの操作

1回の編集で、1文字を挿入、削除、または置換できます。標準的な問題では、各操作のコストはちょうど1です。

状態を定義する

dp[i][j]を、A の最初の i 文字を B の最初の j 文字に変えるために必要な編集回数とします。

一致なら無料

現在の文字がすでに一致していれば、編集は必要ありません。対角の値をそのまま引き継ぎます。

if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1]

それ以外では1を支払う

文字が異なる場合は、最も小さい隣接値を選び、編集1回分を加えます。このmin + 1で3つの操作すべてを扱えます。

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

それぞれの隣接セルが表すもの

上のセルは削除、左のセルは挿入、対角のセルは置換を表します。min は最も安いものを選ぶだけです。

空文字列の初期条件

長さ i の文字列を空にするには、i 回の削除が必要です。そのため、最初の行と列を 0、1、2、… で埋めます。

for i in range(n+1):
    dp[i][0] = i
for j in range(m+1):
    dp[0][j] = j

テーブルのサイズを決める

n+1 行、m+1 列のグリッドを使い、空の接頭辞専用の行と列を用意します。この余白によってループを単純にできます。

dp = [[0] * (m+1) for _ in range(n+1)]

順番に埋める

i と j を1から増やしながらループします。各セルが依存するのは、上、左、対角にある、すでに埋められた隣接セルだけです。

for i in range(1, n+1):
    for j in range(1, m+1):
        ...

距離を読み取る

編集回数の最小値は右下のセルに入ります。テーブルを完成させた後の答えは dp[n][m] です。

distance = dp[n][m]

コストとバリエーション

時間計算量はO(n times m)です。実際の問題では操作ごとに異なるコストを設定することもありますが、同じ漸化式を使えます。

クイックチェック

文字 A[i-1] と B[j-1] は異なります。編集距離を求める漸化式はどれでしょうか。

まとめ：編集距離

一致なら対角の値を引き継ぎ、不一致なら3つの隣接セルのminに1を加えます。境界を初期化して、dp[n][m]を読み取ります。✏️

よくある質問

「編集距離を段階的に学ぶ」レッスンは無料ですか？

はい。「編集距離を段階的に学ぶ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「編集距離を段階的に学ぶ」で何を学びますか？

挿入、削除、置換で変換します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「編集距離を段階的に学ぶ」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. グリッド上の経路数え上げ
  2. 障害物のある最小経路和
  3. 最長共通部分列
  4. 編集距離を段階的に学ぶ
← Competitive Programming Academyに戻る