Thread: Memoization (dyanamic programming) for edit distance recursion

Hey everyone, I am new here. Had a question about my code. I am trying to implement memoization into this program that calculates the levenshtein edit distance of two words. I have the program working correctly without the memozation; however, am otherwise having trouble. Anyone out there spy something I am missing here?

import java.util.ArrayList;
 
 
public class EditDistance {
	public static int CALLS;
    public static boolean MEMOIZING;
    public static ArrayList<String> foundCombination = new ArrayList<String>();
    public static ArrayList<Integer> foundValue = new ArrayList<Integer>();
 
    public static int distance(String s1, String s2){
 
    	CALLS++;
    	//System.out.println(CALLS);
    	//System.out.println(s1 + ", " + s2);
    	//System.out.println(index1 + ", " + index2);
 
    	int[] minCheck = new int[3];
    	int equalChars = 0;
    	int findMin = 0;
    	int tempIndex = 0;
 
 
 
 
		if((s1.length() != 0) && (s2.length() != 0)){
 
			if(MEMOIZING == true && foundCombination.contains(Character.toString(s1.charAt(s1.length()-1)) + Character.toString(s2.charAt(s2.length()-1)))){
				tempIndex = foundCombination.indexOf(Character.toString(s1.charAt(s1.length()-1)) + Character.toString(s2.charAt(s2.length()-1)));
				return foundValue.get(tempIndex);
			}
 
			if(!(s1.substring(s1.length()-1, s1.length()).equals(s2.substring(s2.length()-1, s2.length())))){
				equalChars = 1;
			}
 
			minCheck[0] = distance(s1, s2.substring(0, s2.length()-1)) + 1;
			if(MEMOIZING == true){
				foundCombination.add(Character.toString(s1.charAt(s1.length()-1)) + Character.toString(s2.charAt(s2.length()-1)));
				foundValue.add(minCheck[0]);
			}
			minCheck[1] = distance(s1.substring(0, s1.length()-1), s2) + 1;
			if(MEMOIZING == true){
				foundCombination.add(Character.toString(s1.charAt(s1.length()-1)) + Character.toString(s2.charAt(s2.length()-1)));
				foundValue.add(minCheck[1]);
			}
			minCheck[2] = distance(s1.substring(0, s1.length()-1), s2.substring(0, s2.length()-1)) + equalChars;
			if(MEMOIZING == true){
				foundCombination.add(Character.toString(s1.charAt(s1.length()-1)) +Character.toString(s2.charAt(s2.length()-1)));
				foundValue.add(minCheck[2]);
			}
			findMin = minCheck[0];
 
			for(int i = 1; i < minCheck.length; i++){
				if(minCheck[i] < findMin){
					findMin = minCheck[i];
				}
			}
 
			return findMin;
 
		}
		else{//returning the bigger string length
 
			if(s1.length() > s2.length()){
				return s1.length();
			}else{return s2.length();}
 
		}
 
 
 
    }
}

Here is the Driver for the program

public class tester {
 
	public static void main(String[] args){
	     System.out.println( "--------------------------------------------------") ;
	     EditDistance.MEMOIZING = false ;
	     EditDistance.CALLS = 0 ;
	     System.out.println( EditDistance.distance("socks", "shoes") ) ;
	     System.out.println( EditDistance.CALLS ) ;
	     System.out.println( "--------------------------------------------------") ;
	     EditDistance.MEMOIZING = true ;
	     EditDistance.CALLS = 0 ;
	     System.out.println( EditDistance.distance("socks","shoes") ) ;
	     System.out.println( EditDistance.CALLS ) ;
	     System.out.println(EditDistance.foundCombination);
	     System.out.println(EditDistance.foundValue);
	}
 
}

am otherwise having trouble

What exactly is the trouble? Different output than you expect (please provide expected vs. obtained output)?

If you run the tester class, you see the edit distance for the two words is three and done in roughly 2500 calls. When memorization is flipped to true, you should get the same edit distance value, just done in significantly fewer recursive calls

Originally Posted by rph12

If you run the tester class, you see the edit distance for the two words is three and done in roughly 2500 calls. When memorization is flipped to true, you should get the same edit distance value, just done in significantly fewer recursive calls

So what's the trouble then? Is this not what you expect?

You should expect the same edit distance with fewer calls. You get the fewer calls, just not the correct edit distance.