Created
February 18, 2018 11:44
-
-
Save marcel-goldammer/60c47c6027e3b5a62db80e5316f55175 to your computer and use it in GitHub Desktop.
Levenshtein algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class LevenshteinIterative { | |
| public int distance(String s, String t) { | |
| int[][] distanceMatrix = new int[s.length() + 1][t.length() + 1]; | |
| for (int i = 0; i <= s.length(); i++) { | |
| distanceMatrix[i][0] = i; | |
| } | |
| for (int j = 0; j <= t.length(); j++) { | |
| distanceMatrix[0][j] = j; | |
| } | |
| for (int i = 1; i <= s.length(); i++) { | |
| for (int j = 1; j <= t.length(); j++) { | |
| // calculate cost for substitution | |
| int substCost; | |
| if (s.charAt(i - 1) == t.charAt(j - 1)) { | |
| substCost = 0; | |
| } else { | |
| substCost = 1; | |
| } | |
| distanceMatrix[i][j] = Math.min(distanceMatrix[i - 1][j] + 1, // remove last char from s | |
| Math.min(distanceMatrix[i][j - 1] + 1, // remove last char from t | |
| distanceMatrix[i - 1][j - 1] + substCost)); // remove last char from both s and t | |
| } | |
| } | |
| return distanceMatrix[s.length()][t.length()]; | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class LevenshteinRecursive { | |
| public int distance(String s, String t) { | |
| return distance(s, s.length(), t, t.length()); | |
| } | |
| private int distance(String s, int sLen, String t, int tLen) { | |
| if (sLen == 0) { | |
| return tLen; | |
| } | |
| if (tLen == 0) { | |
| return sLen; | |
| } | |
| // calculate cost for substitution | |
| int substCost; | |
| if (s.charAt(sLen - 1) == t.charAt(tLen - 1) { | |
| substCost = 0; | |
| } else { | |
| substCost = 1; | |
| } | |
| return Math.min(distance(s, sLen - 1, t, tLen) + 1, // remove last char from s | |
| Math.min(distance(s, sLen, t, tLen - 1) + 1, // remove last char from t | |
| distance(s, sLen - 1, t, tLen - 1) + substCost)); // remove last char from both s and t | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment