0

レーベンシュタイン編集距離を実際に計算する必要はないことに注意してください。1かどうかを確認してください。

メソッドのシグネチャは次のようになります。

bool Is1EditDistance(string s1, string s2).

例：1。「abc」と「ab」はtrueを返します2.「abc」と「aebc」はtrueを返します3.「abc」と「a」はfalseを返します

再帰的な承認を試みましたが、効率的ではありません。

更新：友人から回答を得ました：

        for (int i = 0; i < s1.Length && i < s2.Length; i++)
        {
            if (s1[i] != s2[i])
            {
                return s1.Substring(i + 1) == s2.Substring(i + 1)   //case of change
                    || s1.Substring(i + 1) == s2.Substring(i)       //case of s1 has extra
                    || s1.Substring(i) == s2.Substring(i + 1);      //case of s2 has extra
            }
        }
        return Math.Abs(s1.Length - s2.Length) == 1;
4

1 に答える 1

7

距離が正確に 1 かどうかだけを気にする場合は、次のようにすることができます。

  • 文字列の長さの差が 0 または 1 でない場合は、false を返します。
  • 両方の文字列が length の場合、 1 つを除くすべてのチェックをnループします。i = 0..ns1[i] == s2[i]i
  • 文字列の長さnがである場合、 を最小のインデックスにしてn+1、すべてのチェックをループします。is1[i] != s2[i]j=i..ns1[j] == s2[j+1]j
于 2012-09-28T02:58:11.837 に答える