"Edit Distance" algorithm 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&lt;String&gt; 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 &lt; temp[0].length; i++){
            temp[0][i] = i;
        }

        for(int i=0; i &lt; temp.length; i++){
            temp[i][0] = i;
        }

        for(int i=1;i &lt;=str1.length; i++){
            for(int j=1; j &lt;= 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&lt;String&gt; wordList) {
    for (String s : wordList) {
      int dist = dynamicEditDistance(w.toCharArray(), s.toCharArray());
      if (dist &lt; closestDistance || closestDistance == -1) {
        closestDistance = dist;
        closestWords = new LinkedList&lt;String&gt;();
        closestWords.add(s);
      }
      else if (dist == closestDistance)
        closestWords.add(s);
    }
  }

  int getMinDistance() {
    return closestDistance;
  }

  List&lt;String&gt; 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&lt;String&gt; readWordList(BufferedReader input) throws IOException {
    LinkedList&lt;String&gt; list = new LinkedList&lt;String&gt;();
    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&lt;String&gt; 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.
Preliminaries: there's strategy, and there's tactics.
A somewhat common procedure to tackle performance problems is to look at "inner" loops first - not entirely wrong, but the golden rule is
measure.
(And, when turning to others for support, provide measurement results and a test data generator or test data.)  

Some statements regarding edit distance:
• difference in length gives a lower bound on insertions+deletions
• accumulated differences in frequency gives a lower bound on 2*replacements+insertions+deletions



Review proper using m = len(str1) and n = len(str2):  


Document your code. In the code.
design
• I don't like heavyweight constructors
 From the preparation possible, I'd prefer a constructor taking a set of words and
• a "query function" with a word as a parameter (String rather than char[]) -
 too bad returning a multipart result gets verbose, ugly or both in Java
program against interfaces, not implementations
List&lt;String&gt; closestWords;
dynamicEditDistance()  


I can guess what's dynamic about it, but that's an implementation detail; such does not belong in a method name: editDistance()
does not use any instance member: make it static
with "the usual" cost model you don't need a full m×n array
If your edit cost is symmetric (cost(insertion) == cost(deletion) &amp;&amp; cost(replace(a, b)) == cost(replace(b, a))), you don't need previous row(s) and previous column(s).
you iterate the first index in the outer loop and the second one in the inner:
That's the sequence I'd arrange initialisation
(I'd even use j in the 2nd loop)

work currently done in ClosestWords():  


code the way you think about the procedure/solution
- I'd think w doesn't change, let's get the chars exactly once
 (a nifty language system might be doing this for you)
prefer List.clear() over instantiation
(today,) I'd prefer redundantly checking for minimum distance over repeating the add():



          closestWords = new LinkedList&lt;&gt;();
          closestDistance = Integer.MAX_VALUE;
          char[] chars = w.toCharArray();
          for (String s : wordList) {
            int dist = editDistance(chars, s.toCharArray());
            if (dist &lt; closestDistance) {
              closestDistance = dist;
              closestWords.clear();
            }
            if (dist == closestDistance)
              closestWords.add(s);
          }


A "slightly" weirder approach is to handle words from the word list in order of length, first descending from same length, then above and increasing; terminating both when "more extremal length words" can't possibly have a smaller edit distance.
Trying to avoid duplicating the code now extracted as handleDistance() "in line" got out of hand - not pleased, still.
Don't do like I do (not documenting tally (, words) &amp; init()),
do like I say (better than handleDistance() &amp; query(), still)

    final Comparator&lt;String&gt; tally = new Comparator&lt;String&gt;() { @Override
            public int compare(String l, String r) {
                if (l.equals(r))
                    return 0;
                final int ll = l.length(), rl = r.length();
                return ll &lt; rl ? -1
                    : rl &lt; ll ? 1
                      : l.compareTo(r);
            }
        };
    String[] words;
    void init(Collection&lt;String&gt; allWords) {
        words = allWords.toArray(NOSTRINGS);
        Arrays.sort(words, tally);
    }
    /** handles the distance between one pair of &lt;code&gt;String&lt;/code&gt;s
     *  updating &lt;code&gt;closestDistance&lt;/code&gt; and &lt;code&gt;closestWords&lt;/code&gt;
     * @param chars chars of the query &lt;code&gt;String&lt;/code&gt;
     * @param s &lt;code&gt;String&lt;/code&gt; from &lt;code&gt;words&lt;/code&gt;
     */
    void handleDistance(final char[] chars, String s) {
        // System.out.println("&gt;&gt;&gt;" + s + '&lt;');
        final int dist = editDistance(chars, s.toCharArray());
        if (dist &lt; closestDistance) {
            closestDistance = dist;
            closestWords.clear();
        }
        if (dist == closestDistance)
            closestWords.add(s);
    }

    /** queries &lt;code&gt;words&lt;/code&gt; for lowest edit distance to &lt;code&gt;w&lt;/code&gt;
     *  updating &lt;code&gt;closestDistance&lt;/code&gt; and &lt;code&gt;closestWords&lt;/code&gt;
     * @param w &lt;code&gt;String&lt;/code&gt; to find closest words to
     * @return closest words
     */
    public Collection&lt;String&gt; query(String w) {
        final char[] chars = w.toCharArray();
        int sameLength = Arrays.binarySearch(words, w, tally);
        if (0 &lt;= sameLength) {
            closestDistance = 0;
            return closestWords = Collections.singletonList(words[sameLength]);
        }
        closestDistance = Integer.MAX_VALUE;
        sameLength = -sameLength; // insert index + 1
        for (int i = sameLength ; 0 &lt;= --i ; ) {
            final String s = words[i];
            if (closestDistance &lt;= chars.length - s.length())
                break;
            handleDistance(chars, s);
        }
        for (int i = sameLength ; ++i &lt; words.length ; ) {
            final String s = words[i];
            if (closestDistance &lt;= s.length() - chars.length)
                break;
            handleDistance(chars, s);
        }
        return closestWords;
    }