Edit distance 1

Given two strings, how do we check if their edit distance is 1?
Edit distance is defined as the number of characters that needs to be modified, inserted or deleted from one string to transform into the other string.
For example let us consider two strings “java”, “lava” they both differ by just one character. we can change the first character in either of them to make them equal.
Similarly, the words “at”, “bat” also have an edit distance of 1 because either we can add “b” to the first string, or delete “b” from the second string to make them euqal.
By looking at the problem statement, one can think of a dynamic programming solution which takes O(n^2) time. However, it would an over kill to solve this problem.
Let’s observe some thing. Two strings can not have an edit distance of 1 if their lengths differ by more than 1 characters.
So we can simplify our approach to work on the two use cases.
which are either of equal length, or
one string longer than the other by just one character.
Lets see some representative test cases we need to handle.
(“abc”, “bc”), (“abc”, “ab”), (“string”, “sxring”), (“algorithm”, “algoritm”) etc.
If the two strings are equal, we just count the number of mismatches at each index in the two strings.
Otherwise, we check if the shorter string is a sub-sequence of the longer string except one character. In this case we calculate the number matching characters which should be equal to the length of the shorter string.
Here is the Java implementation of the above approach. The time complexity would be linear O(n).

import java.util.Scanner;

public class Solution {
    public static void main(String []args) {
        Scanner reader = new Scanner(System.in);
        String str1 = reader.nextLine();
        String str2 = reader.nextLine();
        if(hasEditDistance1(str1, str2))
            System.out.println("Yes");
        else
            System.out.println("No");
    }

    public static boolean hasEditDistance1(String str1, String str2) {
        if( Math.abs(str1.length()-str2.length()) > 1)
            return false;
        int i, j;

        if(str1.length() == str2.length()) {
            int mismatches = 0;
            for(i = 0; i < str1.length(); i++) {
                if(str1.charAt(i) != str2.charAt(i))
                    mismatches++;
                if(mismatches > 1) {
                    return false;
                }
            }
            return mismatches == 1;
        }
        //Make sure str1 is shorter string
        if(str1.length() > str2.length()) {
            String temp = str1;
            str1 = str2;
            str2 = temp;
        }

        int matched = 0;
        for(i = 0, j = 0; i < str1.length() && j < str2.length(); ) {
            if(str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
                matched++;
            } else {
                j++;

            }
        }
        return matched == str1.length();
    }
}