title: Problems with Levenshtein algorithm in Java
body: <p>I want to use the <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="noreferrer">Levenshtein algorithm</a> for the following task: if a user on my website searches for some value (he enters characters in a input), I want to instantly check for suggestions with AJAX, like Google Instant does. </p>
  
  <p>I have the impression that the Levenshtein algorithm is way too slow for such a task. To check its behaviour, I first implemented it in Java, printing out the two <code>String</code>s in every recursive call of the method.</p>
  
  <pre><code>public class Levenshtein {
      public static void main(String[] arg){
          String a = "Hallo Zusammen";
          String b = "jfdss Zusammen";
  
          int res = levenshtein(a, b);
  
          System.out.println(res);
      }
  
      public static int levenshtein(String s, String t){
          int len_s = s.length();
          int len_t = t.length();
          int cost = 0;
  
          System.out.println("s: " + s + ", t: " + t);
  
          if(len_s&gt;0 &amp;&amp; len_t&gt;0){
              if(s.charAt(0) != t.charAt(0)) cost = 1;
          }
  
          if(len_s == 0){
              return len_t;
          }else{
              if(len_t == 0){
                  return len_s;
              }else{
                  String news = s.substring(0, s.length()-1);
                  String newt = t.substring(0, t.length()-1);
                  return min(levenshtein(news, t) + 1,
                              levenshtein(s, newt) + 1,
                              levenshtein(news, newt) + cost);
              }
          }
      }
  
      public static int min(int a, int b, int c) {
            return Math.min(Math.min(a, b), c);
      }
  }
  </code></pre>
  
  <p>However, here are some points:</p>
  
  <ul>
  <li>The check <code>if(len_s&gt;0 &amp;&amp; len_t&gt;0)</code> was added by me, because I was getting a <code>StringIndexOutOfBoundsException</code> with above test values.</li>
  <li>With above test values, the algorithm seems to calculate infinitely</li>
  </ul>
  
  <p>Are there optimizations that can be made on the algorithm to make it work for me, or should I use a completely different one to accomplish the desired task?</p>