给定两个字符串，找出它们是否相差一个编辑

Question

我最近遇到了这个问题：

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。这将花费 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--;
    }
}

Answer 1

在动态规划方法中，经常会用到矩阵。行对应一个字符串，列对应另一个字符串。重点是找到从左上角单元格到右下角单元格的最便宜路径。在任何一点，水平或垂直过渡代表插入。

你的问题是一样的，只是路径被限制了。使用 k insertions/deletions，路径被限制在 k-对角线上。除此之外，经典的 DP 算法应该可以工作。复杂度是线性的。

Answer 2

这是在 O(n) 中找到一个编辑的解决方案。以下是场景，我已经在实现中进行了介绍。

两个输入字符串的长度差不能超过1。
当字符串长度相同时，不同字符的个数不超过1个
如果长度差为1，则可以在短字符串中插入一个字符，也可以从较长字符串中删除一个字符。考虑到这一点，不同字符的数量不应超过1个。

private static boolean isOneEdit(String first, String second) {
    // if the input string are same
    if (first.equals(second))
        return false;

    int len1 = first.length();
    int len2 = second.length();
    // If the length difference of the stings is more than 1, return false.
    if ((len1 - len2) > 1 || (len2 - len1) > 1  ) {
        return false;
    }
    int i = 0, j = 0;
    int diff = 0;
    while (i<len1 && j<len2) {
        char f = first.charAt(i);
        char s = second.charAt(j);
        if (f != s) {
            diff++;
            if (len1 > len2)
                i++;
            if (len2 > len1)
                j++;
            if (len1 == len2)
                i++; j++;
        }
        else{
            i++; j++;
        }
        if (diff > 1) {
            return false;
        }
    }
    // If the length of the string is not same. ex. "abc" and "abde" are not one edit distance.
    if (diff == 1 && len1 != len2 && (i != len1 || j != len2)) {
        return false;
    }
    return true;
}

Answer 3

在这里您可以找到 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) 时间和常数 space。

Answer 4

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;
    }

Answer 5

    boolean oneEditAway(String first, String second) {
    if (first.length() == second.length()) {
        //call a function which replce the character from the string
    } else if (first.length() + 1 == second.length()) {
        //call a function which remove the character from string
    } else if (first.length() - 1 == second.length()) {
        //call a function which insert the character in the string
    }
    return false;
}

Answer 6

这里是 Ruby 实现：

def one_away(s1, s2)
  return false if (s1.size - s2.size).abs > 1

  missed_count = 0
  counter = 0
  s1.each_char do |c|
    if !s2[counter].nil? && (s2[counter] != c)
      missed_count += 1
    end
    counter += 1
    return false if missed_count > 1
  end
  true
end

p one_away('pale', 'bake') #=> false

Answer 7

答案在Swift中一步步解释：

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

// check if they are the same
if str1 == str2 {
    return true
}

let difference = abs(str1.count - str2.count)

// check if the difference between then is bigger than 1
if difference > 1 {
    return false
}

// lets iterate over the words

var i = 0
var j = 0
var changes = 0

while i < str1.count && j < str2.count {
    let char1 = str1[str1.index(str1.startIndex, offsetBy: i)]
    let char2 = str2[str1.index(str2.startIndex, offsetBy: j)]

    // if the difference is 1 we need to move just one index (the one from the bigger word)
    // this is just necessary when the char1 and char2 are different
    if difference == 1 && char1 != char2 {
        if str1.count > str2.count {
            i += 1
        } else {
            j += 1
        }
        changes += 1
    } else {
        // if chars are equal (in this step we don't care about the difference)
        // we move both indexes.
        i += 1
        j += 1

        if char1 != char2 {
            changes += 1
        }
    }
}

return changes <= 1
}

Answer 8

Java 版本可能如下所示：

public static boolean oneEdit(String w1, String w2) 
{
    char[] word1= w1.trim().toCharArray();
    char[] word2 = w2.trim().toCharArray();

    int length1=word1.length;
    int length2=word2.length;

    if(Math.abs(length2-length1) > 1) return false;

    Arrays.sort(word1);
    Arrays.sort(word2);

    int length = word1.length >= word2.length? word2.length:word1.length; //take the minimum length

    int falseCounter=0;
    for(int i=0; i < length; i++ ) {
        if(word1[i] != word2[i] && ++falseCounter > 1){
            return false;
        }
    }
    return true;
}

Answer 9

C#版本

static bool IsOneEditAway(string word1, string word2)
        {
            if (string.IsNullOrEmpty(word1) && string.IsNullOrEmpty(word2))
                return false;

            ActionType actionToPerform;
            if (word1.Length == word2.Length)
            {
                actionToPerform = ActionType.Replace;
            }
            else if (word1.Length < word2.Length)
            {
                actionToPerform = ActionType.Delete;
            }
            else
                actionToPerform = ActionType.Insert;

            int i = 0, j = 0;
            var numOfEdits = 0;
            var chrWord1 = word1.ToCharArray();
            var chrWord2 = word2.ToCharArray();
            while (numOfEdits <= 1)
            {
                if (i >= chrWord1.Length && j >= chrWord2.Length)
                    break;
                if (i >= chrWord1.Length && j < chrWord2.Length)
                {
                    j++;
                    numOfEdits++;
                    continue;
                }
                if (j >= chrWord2.Length && i < chrWord1.Length)
                {
                    i++;
                    numOfEdits++;
                    continue;
                }
                if (chrWord1[i] == chrWord2[j])
                {
                    i++; j++;
                }
                else
                {
                    switch(actionToPerform)
                    {
                        case ActionType.Insert:
                            i++;
                            break;
                        case ActionType.Delete:
                            j++;
                            break;
                        case ActionType.Replace:
                            i++;j++;
                            break;
                    }
                    numOfEdits++;
                }
            }

            return numOfEdits == 1 ? true : false;
        }
public enum ActionType
    {
        Insert=0,
        Delete=1,
        Replace=2
    }

Answer 10

我在 C++ 中解决了这个问题，它是 Khalid Habib 在 answer. Here is the solution below(I have added this solution on Github too, you can follow the link here) 中试图表达的正确版本。

#include<bits/stdc++.h>
using namespace std;

// checks if there is only one one different in both arrays
bool oneReplaceAway(string s1, string s2){
    bool firstChangeDone = false;
    int l1 = s1.length();
    // l1 == l2 already
    // int l2 = s2.length();
    int l2 = l1;
    int i=0, j=0;

    while(i<l1 && j<l2){
        if(s1[i] != s2[j]){
            // if first change is already checked then return false as there are more than one dissimilarities
            if(firstChangeDone){
                //cout<<"IGI@"<< i<<" "<<j<<"\n";
                return false;   
            }
            firstChangeDone = true;
        }
        i++;
        j++;
    }
    return true;
}


// checks if one word can be added to one string to create the other one
bool oneInsertAway(string s1, string s2){
    bool firstChangeDone = false;
    int l1 = s1.length();
    int l2 = s2.length();

    int i=0, j=0;

    while(i<l1 && j<l2){
        if(s1[i]!=s2[j]){
            // if the chars at i and j are not equal and i!=j, that means one change is already checked, i.e., it is the second change
            if(i!=j)
                return false;
            j++;
        }
        else{
            i++;
            j++;
        }
    }
    return true;
}

// checks of two strings are One Edit Away
bool oneEditAway(string s1, string s2) {
    int l1 = s1.length();
    int l2 = s2.length();

    // cout<<s1<<" - "<<l1<<"\n"<<s2<<" - "<<l2<<"\n"<<(l1==l2)<<"\n";
    if(l1 == l2){
        return oneReplaceAway(s1, s2);
    }
    else if(l1+1 == l2){
        return oneInsertAway(s1, s2);
    }
    else if(l2+1 == l1){
        return oneInsertAway(s2, s1);
    }
    else
        return false;
}


int main(){
    int t;
    cin>>t;

    while(t--){
        string s1,s2;
        cin>>s1>>s2;

        // cout<<oneEditAway(s1, s2)<<"\n";
        string ans = oneEditAway(s1, s2)==1?"One Edit Awway":"Not one Edit Away";
        cout<<ans<<"\n";
    }
    return 0;
}

Answer 11

这是我在 C# 中 O(n) 时间的解决方案。几个场景：

如果字符串长度之差 > 1，则退出
首先遍历第一个字符串，为每个对应的字符递增英文小写数组
然后遍历第二个字符串并递减对应的字符。
最后，检查编辑次数是否大于1...如果是，则中断for循环...

我们将只考虑小写英文字母

public static bool IsStringOneAway(string s1, string s2)
{
    //we will consider lower-case English alphabets only
    int[] engArray = new int[26];
    var tmp = 0;
    var editCount = 0;

    //if string lengths differ by more than 1, then return
    if (Math.Abs(s1.Length - s2.Length) > 1)
    {
        Console.WriteLine("Length difference is more than 1, One Away edit doesn't exist");
        return false;
    }

    //append the english alphabet array from String 1
    for (int i = 0; i < s1.Length; i++)
    {
        tmp = (int)s1[i];
        engArray[tmp - 97]++;
    }

    //deduct the english alphabet arry from String 2
    for (int i = 0; i < s2.Length; i++)
    {
        tmp = (int)s2[i];
        engArray[tmp - 97]--;
    }

    //now check the count of edits; if count > 1, break
    for (int i = 0; i < engArray.Length; i++)
    {
        if (engArray[i] != 0)
        {
            editCount++;
            if (editCount > 2)
            {
                Console.WriteLine("One Away edit doesn't exist");
                return false;
            }
        }
    }

    Console.WriteLine("One Away edit exist");
    return true;

}

Answer 12

这是我的 python 实现。我为每个字符串使用两个数组

 import unittest

# Assume characters stored in 8 bits. 256 possible characters
MAX_CHARS = 256

def is_edit(string1, string2):
    """Given two strings, return if they are one or zero edits away.

    Insert, remove or replace a character."""
    # If the absolute difference in length is more than one
    # return false
    string1_len = len(string1)
    string2_len = len(string2)

    if string1_len != string2_len and abs(string1_len - string2_len) > 1:
        return False

    # Initialize two arrays, each for each string
    count1 = [0] * MAX_CHARS
    count2 = [0] * MAX_CHARS

    # For each character in input strings get unicode representation
    # and  increment counter in corresponding array
    for i in string1:
        count1[ord(i)] += 1

    for i in string2:
        count2[ord(i)] += 1

    edit = 0

    # compare the arrays
    # If number of edits required is more than 2 return false
    # This will handle replacement when given words of the same length
    for i in range(MAX_CHARS):
        if count1[i] != count2[i]:
            edit += 1

        if edit > 2:
            return False

    # Return false if string1 is the same as string2 (No edit required) e.g pale, pale
    if not edit:
        return False

    return True


class EditCheckTestCase(unittest.TestCase):
    """Tests for is_edit method."""

    def test_insert_missing_character(self):
        """Test insertion of character is valid."""
        self.assertEqual(is_edit('pale', 'ple'), True)

    def test_insert_more_than_one_character(self):
        """Test insertion of more than one character is invalid"""
        self.assertEqual(is_edit('pale', 'pe'), False)

    def test_append_one_character(self):
        """Test the append of one character is valid."""
        self.assertEqual(is_edit('pales', 'pale'), True)

    def test_append_more_than_one_character(self):
        """Test append more than one character is invalid."""
        self.assertEqual(is_edit('paless', 'pale'), False)

    def test_replace_one_character(self):
        """Test replacement of one character is valid"""
        self.assertEqual(is_edit('pale', 'bale'), True)

    def test_no_edit_character(self):
        """Test no edit required is valid."""
        self.assertEqual(is_edit('pale', 'bake'), False)
        self.assertEqual(is_edit('pale', 'pale'), False)


if __name__ == "__main__":
    unittest.main()

Answer 13

def isEditDistanceOne(s1, s2):
isoneEdit = False



short = s1 if len(s1) < len(s2) else s2
longg = s2 if len(s1) < len(s2) else s1
if len(longg) - len(short) > 1:
    return False

ind1 = 0
ind2 = 0

while ind1 < len(short) and ind2 < len(longg):
    if short[ind1] != longg[ind2]:
        if isoneEdit:
            return False
        isoneEdit = True

        if len(short) == len(longg):
            ind1 += 1 
    else:
        ind1 += 1 

    ind2 += 1

return True

Answer 14

需要 o(n)运行时间

  public static  boolean isOneEditDistance(String str1 ,String str2 ){
    if(Math.abs(str1.length() - str2.length()) > 1){
        return false;
    }
    String s1 = str1.length() < str2.length() ? str1 : str2; // smallest
    String s2 = str1.length() < str2.length() ? str2 : str1; // biggest
    int index1 = 0, index2 = 0;
    boolean isMoreThanOneEdit = false;

    while (index1 < s1.length() && index2 < s2.length()){
        if(s1.charAt(index1) != s2.charAt(index2)){
            if(isMoreThanOneEdit)
                return false;
            isMoreThanOneEdit = true;
            if(s1.length() == s2.length()) // if replace
                index1++;
        }else {
            index1++; // if match
        }
        index2++; // always longer string index
    }
    return true;
}

Answer 15

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;
}

Answer 16

在 C# 中有一种简单的方法。

    static bool OneEdit(string s1, string s2)
    {
        var diff = s1.Length > s2.Length
                ? s1.Except(s2).ToList()
                : s2.Except(s1).ToList();

        return diff.Count() == 1;
    }

Answer 17

一个Java版本

public class Test {

public static void main(String[] args) {

    System.out.println(fun("car", "cart"));
    System.out.println(fun("cat", "bat"));
    System.out.println(fun("balck", "back"));
}

/*
 * Modifications : add, delete, update
 * 
 * i/p Example Add: a = car b = cart
 * 
 * delete : a = balck b = back
 * 
 * update: a = cat b = bat
 * 
 */
public static boolean fun(String a, String b) {
    Boolean isTestPositive = Boolean.FALSE;
    if (a == null || b == null) {
        return isTestPositive;
    }
    if (a.equals(b)) {
        // No Modifications required
        return isTestPositive;
    }
    // Start comparing
    char[] arrayForA = a.toCharArray();
    char[] arrayForB = b.toCharArray();

    return testCase(arrayForA, arrayForB);

}

public static boolean testCase(char[] a, char[] b) {
    int correctionCount = 0;
    int aLen = a.length;
    int bLen = b.length;
    if (Math.abs(aLen - bLen) > 1) {
        return Boolean.FALSE;
    }
    int minLen = Math.min(aLen, bLen);
    for (int i = 0; i < minLen; i++) {
        if (a[i] != b[i]) {
            ++correctionCount;
            if (correctionCount > 1) {
                return Boolean.FALSE;
            }
            // Test Delete case
            if (b.length > i + 1 && a[i] == b[i + 1]) {
                return testDeleteCase(Arrays.copyOfRange(a, i, a.length - 1),
                        Arrays.copyOfRange(b, i + 1, b.length - 1));
            } else if (a.length > i + 1 && b[i] == a[i + 1]) {
                return testDeleteCase(Arrays.copyOfRange(a, i + 1, a.length - 1),
                        Arrays.copyOfRange(b, i, b.length - 1));
            }

        }

    }
    return Boolean.TRUE;
}

public static boolean testDeleteCase(char[] a, char[] b) {
    int aLen = a.length;
    int bLen = b.length;
    if (Math.abs(aLen - bLen) >= 1) {
        return Boolean.FALSE;
    }
    int minLen = Math.min(aLen, bLen);
    for (int i = 0; i < minLen; i++) {
        if (a[i] != b[i]) {

            return Boolean.FALSE;
        }
    }
    return Boolean.TRUE;
}}

Answer 18

Java 中的通用实现，在 O(N) 中具有所需的编辑次数运行。它确定两个字符串应该小于或等于 edits。

public boolean isEditsAway(String s1, String s2, int edits) {
        int abs = Math.abs(s1.length() - s2.length());
        if (abs > edits)
            return false;

        int edit = 0;
        for (int i = 0; i < s1.length() && i < s2.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i))
                edit++;
            if (edit == edits + 1)
                return false;
        }

        return abs + edit <= edits;
    }

Answer 19

这是我在 JavaScript:

中非常简短的实现

function oneAway(str1, str2) {
    // Check for identical strings
    if (str1 === str2) {
        return true;
    }
    // Check length diff is not more that one char
    if (Math.abs(str2.length - str1.length) > 1) {
        return false;
    }
    // If first characters are equal, check following substring
    if (str1[0] === str2[0]) {
        return oneAway(str1.slice(1), str2.slice(1));
    } else {
        // Check first character edition
        if (str1.length === str2.length && str1 === str1[0] + str2.slice(1)) {
            return true;
        }
        // Check first character deletion
        else if (str1.length > str2.length && str1 === str1[0] + str2) {
            return true;
        }
        // Check first character insertion
        else if (str1.length < str2.length && str1 === str2.slice(1)) {
            return true;
        }
    }
    return false;
}

这是测试结果，对比“苍白”：

pale true
pae true
pal true
ple true
ale true
xale true
pxle true
paxe true
palx true
xpale true
palex true
xxle false
pxxe false
paxx false
xalx false
xaxe false
palexx false
le false

Answer 20

检查我的 C# 解决方案 O(n) 时间复杂度

 public static bool IsOneEdit(string val1, string val2)
        {
            if (val1 == null || val2 == null || val1.Equals(val2) || val1.Except(val2).Count() > 1 || val2.Except(val1).Count() > 1)
                return false;

            var len1 = val1.Length;
            var len2 = val2.Length;

            if (Math.Abs(len1 - len2) > 1)
                return false;

            //replace operation
            if (len1 == len2)
            {
                for (int i = 0; i < len1; i++)
                {
                    if(val2[i] != val1[i])
                    {
                        if(val1 == val2.Remove(i, 1).Insert(i, val1[i].ToString()))
                        {
                            return true;
                        }
                    }
                }
            }
            else
            {
                var bigOne = len1 > len2 ? val1 : val2;
                var smallOne = len1 < len2 ? val1 : val2;

                for (int i = 0; i < bigOne.Length; i++)
                {
                    if(bigOne.Remove(i,1) == smallOne)
                    {
                        return true;
                    }
                }
            }
            return false;
        }

给定两个字符串，找出它们是否相差一个编辑

Given two strings, find if they are one edit away from each other

string

algorithm

edit-distance