10

私は最近この質問に出くわしました：

Given two strings, return true if they are one edit away from each other,else return false.
An edit is insert/replace/delete a character. 
Ex. {"abc","ab"}->true, {"abc","adc"}->true, {"abc","cab"}->false

この問題を解決する 1 つの方法は、動的計画法を使用して 2 つの文字列間の編集距離を見つけ、それが 1 かどうかを確認することです。これには O(N2) 時間かかります。1編集離れているかどうかを確認するだけなので、線形時間でこれを行う方法はありますか?

以下に書いたコードはほとんどの場合に機能しますが、{"m",""} のような場合には失敗します

public boolean isOneEditDistance(String s1,String s2){
    if(s1==null || s2==null)
        return true;
    if(s1.equals(s2))
        return false;
    if (Math.abs(s1.length() - s2.length()) > 1)
        return false;
    int i = -1;
    int j = -1;
    while (true)
    {
        i++;
        j++;
        if (i == s1.length())
            return true;
        if (s1.charAt(i) == s2.charAt(j))
            continue;
        if (i != j)
            return false;
        if (s1.length() < s2.length())
            i--;
        else
            j--;
    }
}
4

20 に答える 20

4

動的計画法では、行列がよく使われます。行は 1 つの文字列に対応し、列は別の文字列に対応します。ポイントは、左上のセルから右下のセルへの最も安いパスを見つけることです。どの時点でも、水平または垂直遷移は挿入を表します。

問題は同じですが、パスが制限されています。k回の挿入/削除により、パスはk対角に制限されます。それ以外は、従来の DP アルゴリズムが機能するはずです。複雑さは線形です。

于 2015-09-07T05:17:42.490 に答える
1 
static boolean isEditDistanceOne(String s1, String s2)
    {
        // Find lengths of given strings
        int m = s1.length(), n = s2.length();

        // If difference between lengths is more than
        // 1, then strings can't be at one distance
        if (Math.abs(m - n) > 1)
            return false;

        int count = 0; // Count of edits

        int i = 0, j = 0;
        while (i < m && j < n)
        {
            // If current characters don't match
            if (s1.charAt(i) != s2.charAt(j))
            {
                if (count == 1)return false;

                // If length of one string is
                // more, then only possible edit
                // is to remove a character
                if (m > n) i++;
                else if (m< n) j++;
                else //Iflengths of both strings is same
                {
                    i++;
                    j++;
                }

                // Increment count of edits 
                count++;
            }

            else // If current characters match
            {
                i++;
                j++;
            }
        }

        // If last character is extra in any string
        if (i < m || j < n)
            count++;

        return count == 1;
    }
于 2016-05-12T20:51:10.340 に答える
0

ここでは、Swift での解決率を確認できます。

func isOneEdit(str1: String, str2: String) -> Bool {

  //The length difference between two input strings should not be more than 1.
  let diff = abs(str1.characters.count - str2.characters.count)
  if diff > 1 {
    return false
  }

  //When the length of the strings is same, the number of different chars should not be more than 1.
  if diff == 0 {
    var numberOfEdits = 0
    for (char1, char2) in zip(str1.characters, str2.characters) {
      if char1 != char2 {
        numberOfEdits++
      }
    }
    return numberOfEdits < 2
  }

  //If the length difference is 1.
  //then either one char can be inserted in the short string or deleted from the longer string. 
  //Considering that, the number of different char should not be more than 1.

  return str1.rangeOfString(str2) != nil || str2.rangeOfString(str1) != nil



  //return str1.isSubstring(str2) || str2.isSubstring(str1)

}

この関数は O(n) 時間と一定のスペースを必要とします。

于 2016-01-06T21:59:12.623 に答える
0 
public static Boolean isOneAway(String s1, String s2) {
    if (s1.equals(s2))
        return true;
    char[] s1Array = s1.toCharArray();
    char[] s2Array = s2.toCharArray();
    if (s1Array.length == s2Array.length) {
        int differingElementsCount = 0;
        for (Character c1 : s1Array) {
            boolean exists = false;
            for (Character c2 : s2Array) {
                if (!c1.equals(c2)) {
                    continue;
                } else {
                    if (s1.lastIndexOf(c1) == s2.indexOf(c2)) {
                        exists = true;
                        break;
                    } else {
                        differingElementsCount++;
                        continue;
                    }
                }
            }
            if (exists == false) {
                differingElementsCount++;
            }
        }
        if (differingElementsCount > 1) {
            return false;
        }
    } else if (s1Array.length > s2Array.length) {
        if ((s1Array.length - s2Array.length) > 1) {
            return false;
        } else {
            return true;
        }
    } else {
        if (s2Array.length - s1Array.length > 1) {
            return false;
        } else {
            return true;
        }
    }
    return true;
}
于 2020-08-02T12:27:33.607 に答える