Created
September 11, 2019 07:26
-
-
Save tjkhara/11149e392929f2618e762b0e3c541e61 to your computer and use it in GitHub Desktop.
Edit distance java code
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 EditDistance { | |
| /** | |
| * Returns the EditDistance between source and target string | |
| * @param source | |
| * @param target | |
| * @return | |
| */ | |
| public int editDistanceBetween(String source, String target) { | |
| if (source == null || target == null){ | |
| throw new IllegalArgumentException("Input strings cannot be null"); | |
| } | |
| int sourceLength = source.length(); | |
| int targetLength = target.length(); | |
| Integer[][] E = new Integer[sourceLength+1][targetLength+1]; | |
| for (int i = 0; i <= sourceLength; i++ ){ | |
| E[i][0] = i; | |
| } | |
| for (int j = 0; j <= targetLength; j++ ){ | |
| E[0][j] = j; | |
| } | |
| for (int i = 1; i <= sourceLength; i++){ | |
| for (int j = 1; j <= targetLength; j++){ | |
| int cost = source.charAt(i - 1) == target.charAt(j - 1) ? 0 : 1; | |
| E[i][j] = Math.min( Math.min( E[i-1][j-1] + cost, E[i][j-1] + 1), E[i-1][j] + 1); | |
| } | |
| } | |
| return E[sourceLength][targetLength]; | |
| } | |
| public static void main(String[] args){ | |
| EditDistance editDistance = new EditDistance(); | |
| System.out.println("EditDistance from Ankit to Amita is " + | |
| editDistance.editDistanceBetween("Ankit", "Amita")); | |
| System.out.println("EditDistance from Ankita to Nikita is " | |
| + editDistance.editDistanceBetween("Ankita", "Nikita")); | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment