C++で2つの文字列が「1回の編集距離」かどうかを判定する方法

問題の概要

2つの文字列 s と t が与えられたとき、両者が「1回の編集距離(ワン・エディット・ディスタンス)」の関係にあるかどうかを判定します。ここでいう1回の編集距離とは、次の3種類の操作をちょうど1回だけ適用することで、一方の文字列からもう一方の文字列を作れることを意味します。

• s に1文字を挿入して t を得る
• s から1文字を削除して t を得る
• s の1文字を別の文字に置き換えて t を得る

たとえば、入力が s = "ab"、t = "acb" の場合を見てみましょう。"ab" の2文字目に "c" を挿入すれば "acb" になるため、このケースの出力は True(真)となります。

解法のアプローチ

この問題は、以下の手順で効率よく解くことができます。

1. n := s の長さ、m := t の長さとします。
2. n < m の場合は、引数を入れ替えて isOneEditDistance(t, s) を返します。これにより、常に s の方が長い(または等しい)状態で処理できます。
3. i を 0 から m - 1 までループし、最初に文字が異なる位置を探します。
   • s[i] != t[i] が見つかった場合:
     • n == m(同じ長さ)なら、残りの部分文字列 s.substr(i + 1) と t.substr(i + 1) が一致するかを確認します(置換のケース)。
     • 長さが異なる場合は、s.substr(i + 1) と t.substr(i) が一致するかを確認します(挿入・削除のケース)。
4. ループが最後まで終わった場合は、m + 1 == n を返します。これは「s が t よりちょうど1文字長く、末尾以外は完全に一致している」ケースに対応します。

このアルゴリズムの計算量は O(n)、空間計算量は O(1) であり、非常に効率的です。

C++での実装例

それでは、実際の実装を見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int n = s.size();
        int m = t.size();
        if (n < m) {
            return isOneEditDistance(t, s);
        }
        for (int i = 0; i < m; i++) {
            if (s[i] != t[i]) {
                if (n == m) {
                    return s.substr(i + 1) == t.substr(i + 1);
                }
                return s.substr(i + 1) == t.substr(i);
            }
        }
        return m + 1 == n;
    }
};
main(){
    Solution ob;
    cout << (ob.isOneEditDistance("ab", "acb"));
}

入力例

s = "ab", t = "acb"

出力例

1

出力が 1(true)となっており、"ab" と "acb" が1回の挿入操作で変換可能であることが正しく判定されています。