Skip to content

Instantly share code, notes, and snippets.

@BullyBoo
Created April 13, 2020 16:21
Show Gist options
  • Save BullyBoo/c074b205fbf3d18158a5a40bc9ef8506 to your computer and use it in GitHub Desktop.
Save BullyBoo/c074b205fbf3d18158a5a40bc9ef8506 to your computer and use it in GitHub Desktop.
String similar algorithm
public static int similar(String checkable, String original){
int checkableLength = checkable.length();
int originalLength = original.length();
int[] checkableArray;
int[] originalArray = new int[originalLength + 1];
for(int i = 0; i <= originalLength; i++) {
originalArray[i] = i;
}
for(int i = 1; i <= checkableLength; i++) {
checkableArray = originalArray;
originalArray = new int[originalLength + 1];
for(int j = 0; j <= originalLength; j++) {
if(j == 0){
originalArray[j] = i;
} else {
int cost = (checkable.charAt(i - 1) != original.charAt(j - 1)) ? 1 : 0;
if(originalArray[j - 1] < checkableArray[j]
&& originalArray[j - 1] < checkableArray[j - 1] + cost) {
originalArray[j] = originalArray[j - 1] + 1;
} else if(checkableArray[j] < checkableArray[j - 1] + cost) {
originalArray[j] = checkableArray[j] + 1;
} else {
originalArray[j] = checkableArray[j - 1] + cost;
}
}
}
}
return originalArray[originalLength];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment