Untitled

mail@pastecode.io avatar
unknown
java
7 months ago
707 B
3
Indexable
Never
 static int partDist(String w1, String w2, int w1len, int w2len,int[][] m) {
    
    if(m[w2len][w1len] > -1) //check if we already know answer
      return m[w2len][w1len];
   
    if (w1len == 0)
      return w2len;
    if (w2len == 0)
      return w1len;

    int res = partDist(w1, w2, w1len - 1, w2len - 1,m) + 
	  (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);

    int addLetter = partDist(w1, w2, w1len - 1, w2len,m) + 1;
    
    if (addLetter < res)
      res = addLetter;
    
    int deleteLetter = partDist(w1, w2, w1len, w2len -1,m) + 1;
    
    if (deleteLetter < res)
      res = deleteLetter;

    m[w2len][w1len] = res; //save answer
    return res;
  }