Skip to content

Instantly share code, notes, and snippets.

@ravichandrae
Last active November 27, 2017 13:51
Show Gist options
  • Save ravichandrae/48ce5631b95374e56436d859f70cd24f to your computer and use it in GitHub Desktop.
Save ravichandrae/48ce5631b95374e56436d859f70cd24f to your computer and use it in GitHub Desktop.
Given two strings, how do we check if their edit distance is 1?
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment