編集距離（レーベンシュタイン距離）とは？
編集距離（レーベンシュタイン距離）とは、一方の文字列を他方に変えるために必要な、1文字の挿入・削除・置換の最小回数。文字列の似ている度合いを数値化する尺度で、2つの文字列の長さをn、mとすると表を埋める方式でO(nm)の時間と領域で求められる。
へんしゅうきょり
編集距離（レーベンシュタイン距離）の意味
一方の文字列を他方に変えるために必要な、1文字の挿入・削除・置換の最小回数。文字列の似ている度合いを数値化する尺度で、2つの文字列の長さをn、mとすると表を埋める方式でO(nm)の時間と領域で求められる。
編集距離（レーベンシュタイン距離）の具体例
「kitten」と「sitting」の編集距離は3（k→s、e→i、末尾にg挿入）。検索語の打ち間違いに対する「もしかして」候補の提示、名寄せでの表記ゆれ判定、スペルチェッカの候補生成などに使われる。
編集距離（レーベンシュタイン距離）は試験でどう引っ掛けられる？
表の各マスが「直前3マスの最小値＋コスト」で決まる典型的な動的計画法であり、貪欲に1文字ずつ合わせても最小にはならない。また置換を許さない定義や重み付きの定義もあるため、問題文の操作の定義を必ず確認する。
編集距離（レーベンシュタイン距離）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。