User:Mwn3d/Levenshtein distance
This is wrong. It's an attempt at a recursive version of Levenshtein distance. I'll be working on it myself on the side, but if anyone wants to help they can talk about it or directly edit it here.
It tries an exhaustive search of possibilities from string a to get to string b. It will either insert a character from string b into the right position in a, delete an unneeded character from a, or change a character in a to the corresponding on from string b to generate possibilities. It does this one possibility at a time and calls itself to see if it got any closer. <lang java5>import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set;
public class Dist {
public static int lDist(String a, String b) throws Exception{ if(a == null || b == null){ return -1; //error }
if(a.equals(b)) return 0;
if(a.length() == 0){ return b.length(); } if(b.length() == 0){ return a.length(); }
//keep track of the scores for each candidate Map<String, Integer> mem = new HashMap<String, Integer>();
StringBuilder aBuff = new StringBuilder(a);
//set so we don't test the same candidate twice Set<String> candidates = new HashSet<String>();
if (a.length() < b.length()) {//if a is longer than b generate all possible deletion possibilities for (int i = 0; i < a.length(); i++) { //insert candidates.add(aBuff.insert(i + 1, b.charAt(i + 1)).toString()); aBuff.deleteCharAt(i + 1); } }
if(a.length() > b.length()){//if a is short than b generate all insertion possibilities for(int i = 0; i < a.length(); i++){ //remove char temp = aBuff.charAt(i); candidates.add(aBuff.deleteCharAt(i).toString()); aBuff.insert(i, temp); } }
if (a.length() == b.length()) {//if they are the same length generate all possible change possibilities for (int i = 0; i < a.length(); i++) { //change if (aBuff.charAt(i) != b.charAt(i)) { char temp = aBuff.charAt(i); candidates.add(aBuff.replace(i, i + 1, Character.toString(b.charAt(i))).toString()); aBuff.replace(i, i + 1, Character.toString(temp)); } } }
for(String candidate: candidates){ mem.put(candidate, 1 + lDist(candidate, b)); }
int ans = Integer.MAX_VALUE;
for(String candidate: mem.keySet()){ if(mem.get(candidate) < ans){ ans = mem.get(candidate); } }
return ans; }
public static void main(String[] args) throws Exception{ System.out.println(lDist("kitten", "sitting")); //prints 3, which is correct System.out.println(lDist("nettik", "gnittis")); //prints 4, which doesn't make sense }
}</lang>