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);
	}
 
}