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

10

这是在 O(n) 中找到一个编辑的解决方案。下面是我在实现中介绍的场景。

  1. 两个输入字符串之间的长度差不应大于 1。
  2. 当字符串长度相同时，不同字符的个数不应超过 1。
  3. 如果长度差为 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;
}
于 2015-09-07T05:25:47.197 回答
4

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

您的问题是相同的，但路径受到限制。对于k个插入/删除，路径被限制在k对角线中。除此之外，经典的 DP 算法应该可以工作。复杂度是线性的。

于 2015-09-07T05:17:42.490 回答
2

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;
}
于 2019-01-29T22:38:38.203 回答
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 回答
1

我用C++解决了这个问题，这是 Khalid Habib 在这个答案中试图说的正确版本。这是下面的解决方案（我也在Github上添加了这个解决方案，你可以点击这里的链接）。

#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;
}
于 2019-03-19T04:06:13.603 回答
1

一个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;
}}
于 2020-12-07T12:14:27.707 回答
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 
    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;
}
于 2017-10-07T12:38:30.133 回答
0

这是 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
于 2017-11-19T11:12:16.030 回答
0

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
}
于 2017-11-26T04:39:09.900 回答
0

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
    }
于 2019-03-08T01:04:43.183 回答
0

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

  • 如果字符串长度差> 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;

}
于 2019-08-17T17:02:34.013 回答
0

这是我的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()
于 2019-08-19T06:05:26.720 回答
0 
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
于 2019-09-11T04:26:02.080 回答
0

它将花费 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;
}
于 2020-03-19T13:35:30.477 回答
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 回答
0

在 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;
    }
于 2020-10-13T07:46:25.810 回答
0

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;
    }
于 2021-01-17T13:36:52.770 回答
0

这是我在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
于 2021-09-13T19:17:42.400 回答
0

检查我的 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;
        }
于 2022-01-14T17:43:57.890 回答