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

Solution 1:

Here is the solution for finding the one edit in O(n). Below are the scenario, I have covered in the implementation.

1. The length difference between two input strings should not be more than 1.
2. When the length of the strings is same, the number of different chars should not be more than 1.
3. 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.

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

Solution 2:

In the dynamic programming method, frequently a matrix is used. The rows correspond to one string, and the columns to the other. The point is to find the cheapest path from the top-left cell to the bottom right. At any point, a horizontal or vertical transition stands for an insertion.

Your problem is the same, but the paths are restricted. With k insertions/deletions, the path is restricted to be in the k-diagonal. Other than that, the classical DP algorithm should work. The complexity is linear.

Solution 3:

Java version may be like below:

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

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