C++での1つの編集距離

2つの文字列sとtがあるとします。両方が1つの編集距離だけ離れているかどうかを確認する必要があります。 1つの編集距離には3つのタイプがあります-

• sに文字を挿入してtを取得します

• sから文字を削除してtを取得します

• sの文字を置き換えてtを取得します

したがって、入力がs ="ab"、t ="acb"の場合、出力はTrueになります

これを解決するには、次の手順に従います-

• n：=sのサイズ、m：=tのサイズ

• n

  • isOneEditDistance（t、s）を返す

• 初期化i：=0の場合、i

  • s[i]がt[i]と等しくない場合、-

    • nがmと同じ場合、-

      • インデックス0から（i）までのsのサブストリングが、インデックス0から（i）までのtのサブストリングと同じである場合にtrueを返します

    • インデックス0から（i）までのsのサブストリングが、インデックス0から（i-1）までのtのサブストリングと同じである場合にtrueを返します

• m+1がnと同じ場合はtrueを返します

例

理解を深めるために、次の実装を見てみましょう-

#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