/* Labb 2 i DD1352 Algoritmer, datastrukturer och komplexitet    */
/* Se labbanvisning under kurswebben https://www.kth.se/social/course/DD1352 */
/* Ursprunglig författare: Viggo Kann KTH viggo@nada.kth.se      */
import java.util.LinkedList;
import java.util.List;

public class ClosestWords {
  LinkedList<String> closestWords = null;

  int closestDistance = -1;

  int partDist(String w1, String w2, int w1len, int w2len) {
    if (w1len == 0)
      return w2len;
    if (w2len == 0)
      return w1len;
    int res = partDist(w1, w2, w1len - 1, w2len - 1) + 
	(w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);
    int addLetter = partDist(w1, w2, w1len - 1, w2len) + 1;
    if (addLetter < res)
      res = addLetter;
    int deleteLetter = partDist(w1, w2, w1len, w2len - 1) + 1;
    if (deleteLetter < res)
      res = deleteLetter;
    return res;
  }

  int Distance(String w1, String w2) {
    return partDist(w1, w2, w1.length(), w2.length());
  }

  public ClosestWords(String w, List<String> wordList) {
    for (String s : wordList) {
      int dist = Distance(w, s);
      // System.out.println("d(" + w + "," + s + ")=" + dist);
      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;
  }
}

@@ -368,24 +368,24 @@
 %0A%0A  int 
-part
 Dist
+ance
 (String 
@@ -432,140 +432,288 @@
    i
-f (w1len == 0)%0A      return w2len;%0A    if (w2len == 0)%0A      return w1
+nt i;%0A    int j;%0A    int%5B%5D%5B%5D matrix = new int%5Bw1len+1%5D%5Bw2len+1%5D;%0A%0A    for (i = 0; i %3C= w1len; i++) %7B%0A      matrix%5Bi%5D%5B0%5D = i;%0A    %7D%0A    for (j = 0; j %3C= w2
 len;
-%0A    int res = partDist(w1, w2, w1len - 1, w2len - 1) + %0A%09
+ j++) %7B%0A      matrix%5B0%5D%5Bj%5D = j;%0A    %7D%0A%0A    for (i = 1; i %3C= w1len; i++) %7B%0A      for (j = 1; j %3C= w2len; j++) %7B%0A        if 
 (w1.
@@ -719,24 +719,18 @@
 .charAt(
-w1len - 
+i-
 1) == w2
@@ -741,367 +741,276 @@
 rAt(
-w2len - 1) ? 0 : 1);%0A    int addLetter = partDist(w1, w2, w1len - 1, w2len) + 1;%0A    if (addLetter %3C res)%0A      res = addLetter;%0A    int deleteLetter = partDist(w1, w2, w1len, w2len - 1) + 1;%0A    if (deleteLetter %3C res)%0A      res = deleteLetter;%0A    return res;%0A
+j-1)) %7B%0A          matrix%5Bi%5D%5Bj%5D = matrix%5Bi-1%5D%5Bj-1%5D;%0A        %7D else if (matrix%5Bi-1%5D%5Bj%5D %3C matrix%5Bi%5D%5Bj-1%5D) %7B%0A          matrix%5Bi%5D%5Bj%5D = 1 + matrix%5Bi-1%5D%5Bj%5D;%0A        %7D else  %7B%0A          matrix%5Bi%5D%5Bj%5D = 1 + matrix%5Bi%5D%5Bj-1%5D;%0A      
   %7D%0A
-%0A
   
-int Distance(String w1, String w2) %7B%0A    return partDist(w1, w2, w1.length(), 
+    %7D%0A    %7D%0A    return matrix%5Bw1len%5D%5B
 w2
-.
 len
-gth())
+%5D
 ;%0A  
@@ -1131,16 +1131,40 @@
 nce(w, s
+, w.length(), s.length()
 );%0A     

Add beining of DynProg