文字列間の編集距離が1かどうかを判定する方法

文字列の編集距離を判定する方法について解説します。具体的には、2つの文字列が与えられたとき、1回の編集で一方の文字列を他方に変換できるかどうかを判定するアルゴリズムを紹介します。

編集距離とは？

文字列間の編集距離とは、ある文字列を別の文字列に変換するために必要な編集操作の最小回数のことです。編集操作には、以下の3種類があります。

1. 文字の挿入
2. 文字の削除
3. 文字の置換

この記事では、編集距離が1であるかどうかを判定することに焦点を当てています。つまり、1回の挿入、削除、または置換で一方の文字列を他方に変換できるかどうかを判定します。

編集距離が1かどうかを判定する

2つの文字列 s1 と s2 が与えられたとき、s1 を s2 に変換するのに必要な編集回数が1回であるかどうかを判定します。

例:

Input: s1 = "geeks", s2 = "geek"
Output: yes (1文字削除)

Input: s1 = "geeks", s2 = "geeks"
Output: no (編集不要)

Input: s1 = "geaks", s2 = "geeks"
Output: yes (1文字置換)

Input: s1 = "peaks", s2 = "geeks"
Output: no (2文字変更が必要)

実装方法 (C++)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool isEditDistanceOne(string s1, string s2) {
    int m = s1.length(), n = s2.length();

    // 長さの差が1より大きい場合は編集距離は1ではない
    if (abs(m - n) > 1)
        return false;

    int count = 0; // 編集回数
    int i = 0, j = 0;

    while (i < m && j < n) {
        if (s1[i] != s2[j]) {
            // 編集回数が1を超えたらfalse
            if (count == 1)
                return false;

            // 長さが異なる場合は、長い方の文字列のインデックスを進める
            if (m > n)
                i++;
            else if (m < n)
                j++;
            else {
                // 同じ長さの場合は、両方のインデックスを進める
                i++;
                j++;
            }

            // 編集回数をインクリメント
            count++;
        } else {
            // 文字が一致する場合は、両方のインデックスを進める
            i++;
            j++;
        }
    }

    // どちらかの文字列に余分な文字が残っている場合
    if (i < m || j < n)
        count++;

    return count == 1;
}

int main() {
    string s1 = "gfg";
    string s2 = "gf";

    if (isEditDistanceOne(s1, s2))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

コードの解説

1. 長さのチェック: 2つの文字列の長さの差が1より大きい場合、編集距離が1になることはありません。したがって、false を返します。
2. 同時トラバース: 2つの文字列を同時にトラバースし、異なる文字の数をカウントします。
3. 編集回数のカウント: 異なる文字が見つかった場合、編集回数をインクリメントします。編集回数が1を超えた場合、false を返します。
4. 長さの違いの処理: 文字列の長さが異なる場合、長い方の文字列のインデックスを進めます（挿入または削除の場合）。文字列の長さが同じ場合、両方のインデックスを進めます（置換の場合）。
5. 余分な文字の処理: どちらかの文字列に余分な文字が残っている場合、編集回数をインクリメントします。
6. 結果の判定: 最終的な編集回数が1である場合、true を返します。それ以外の場合は、false を返します。

様々なプログラミング言語での実装

上記のアルゴリズムは、C++、Java、Python3、C#、Javascript など、さまざまなプログラミング言語で実装できます。この記事では、GeeksforGeeks に掲載されている各言語でのサンプルコードを以下に示します。

• C++
• Java
• Python3
• C#
• Javascript

まとめ

この記事では、2つの文字列間の編集距離が1であるかどうかを判定する効率的なアルゴリズムについて説明しました。このアルゴリズムは、様々なアプリケーションで使用できます。