I have a piece of code that calculates the edit distance between words and works, but it's apparently not fast enough.
ClosestWords.java:
import java.util.LinkedList;
import java.util.List;
public class ClosestWords {
LinkedList<String> closestWords = null;
int closestDistance = -1;
public int dynamicEditDistance(char[] str1, char[] str2){
int temp[][] = new int[str1.length+1][str2.length+1];
for(int i=0; i < temp[0].length; i++){
temp[0][i] = i;
}
for(int i=0; i < temp.length; i++){
temp[i][0] = i;
}
for(int i=1;i <=str1.length; i++){
for(int j=1; j <= str2.length; j++){
if(str1[i-1] == str2[j-1]){
temp[i][j] = temp[i-1][j-1];
}else{
temp[i][j] = 1 + Math.min(temp[i-1][j-1], Math.min(temp[i-1][j], temp[i][j-1]));
}
}
}
return temp[str1.length][str2.length];
}
public ClosestWords(String w, List<String> wordList) {
for (String s : wordList) {
int dist = dynamicEditDistance(w.toCharArray(), s.toCharArray());
if (dist < closestDistance || closestDistance == -1) {
closestDistance = dist;
closestWords = new LinkedList<String>();
closestWords.add(s);
}
else if (dist == closestDistance)
closestWords.add(s);
}
}
int getMinDistance() {
return closestDistance;
}
List<String> getClosestWords() {
return closestWords;
}
}
Main.java:
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static List<String> readWordList(BufferedReader input) throws IOException {
LinkedList<String> list = new LinkedList<String>();
while (true) {
String s = input.readLine();
if (s.equals("#"))
break;
list.add(s);
}
return list;
}
public static void main(String args[]) throws IOException {
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in, "UTF-8"));
List<String> wordList = readWordList(stdin);
String word;
while ((word = stdin.readLine()) != null) {
ClosestWords closestWords = new ClosestWords(word, wordList);
System.out.print(word + " (" + closestWords.getMinDistance() + ")");
for (String w : closestWords.getClosestWords())
System.out.print(" " + w);
System.out.println();
}
}
}
Example input:
skål
skålar
skålen
skålens
skålform
#
kål
k
b
sklfrm
skala
Example Output:
kål (1) skål
k (3) skål
b (4) skål
sklfrm (2) skålform
skala (2) skål skålar
The upper part of the input are all the "correct" words and the lower part of the input (below the '#') are the words that need to be corrected. The output lines are of the form:
misspeltWord (minEditDistance)
listOfPossibleCorrectWordsThatShareTheSameEditDistance
Is there a way to make this code more efficient? I am running the code through a sort of "speed test" and it keeps failing on the last part of the test.
How can I optimize my “Edit Distance” algorithm/code?
which applies to too many questions on code review. \$\endgroup\$ – pacmaninbw Jan 20 '20 at 17:40apparently not fast enough
the motivation to improve this code was stronger/more focused if the question spelled out what made lacking speed apparent. If this was a rating in some programming challenge: there is a tag programming-challenge. \$\endgroup\$ – greybeard Jan 21 '20 at 7:39