Levenshtein distance

mail@pastecode.io avatar
unknown
java
7 months ago
831 B
2
Indexable
Never
public int partDist(String w1, String w2, int[][]m) {
  
    int subCost = 0;
    for(int j = 1; j < w2.length()+1;j++)
    {
      for(int i = 1; i < w1.length()+1; i++)
      {
        if(w1.charAt(i-1)==w2.charAt(j-1))
          subCost = 0;

        else
          subCost = 1;

        m[i][j] = Math.min(m[i-1][j] + 1, //delete a character 
                  Math.min(m[i][j-1] + 1, //insert a character
                  m[i-1][j-1] + subCost));//sub a character
        
      }
    }
    return m[w1.length()][w2.length()];
  }

  int distance(String w1, String w2) {
    int[][] m = new int[w1.length()+1][w2.length()+1];
    for(int i = 1; i < 1 + w1.length();i++)
      m[i][0] = i;
      
    for(int i = 1; i < 1 + w2.length();i++)
      m[0][i] = i;

    return partDist(w1, w2,m);
  }