View Javadoc

1   /*
2    * To change this template, choose Tools | Templates
3    * and open the template in the editor.
4    */
5   
6   package net.sf.zel.math;
7   
8   import static java.lang.Math.*;
9   
10  
11  /**
12   *
13   * @author zoly
14   */
15  public final class StringUtil {
16  
17      private StringUtil() {}
18      /**
19       * function that calculates the number of operations that are needed to
20       * transfor s1 into s2.
21       * operations are: char add, char delete, char modify
22       * @param s1
23       * @param s2
24       * @return the number of operations required to transfor s1 into s2
25       */
26      public static int distance(final String s1, final String s2)
27      {
28          int l1 = s1.length();
29          int l2 = s2.length();
30          
31          int []  prev = new int [l2];
32          char c1 = s1.charAt(0);
33          prev[0] = distance(c1, s2.charAt(0));
34          for (int j =1; j< l2; j++)
35              prev[j] =  prev[j-1] + distance(c1, s2.charAt(j));
36  
37          for (int i = 1 ; i< l1; i++)
38          {
39              int []  dist = new int [l2];
40              c1 = s1.charAt(i);
41              dist[0] = prev[i-1] + distance(c1, s2.charAt(0));
42              for (int j =1; j< l2; j++)
43                  dist[j] = min ( prev[j-1] + distance(c1, s2.charAt(j)),
44                          min ( prev[j] + 1, dist[j-1] + 1 ));
45              prev = dist;
46          }
47          return prev[l2-1];
48      }
49  
50      public static final int distance(final char c1, final char c2)
51      {
52          if (c1 == c2)
53              return 0;
54          else
55              return 1;
56      }
57  
58  }