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