Edit distance is a way of quantifying how dissimilar two strings are to one another by counting the minimum number of operations required to transform one string into the other.
source Code
package com.dsacode.Algorithm.dynamic; public class EditDistance { public static int getEditDistance(String a, String b) { int m = a.length(); int n = b.length(); int[][] len = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) { len[i][0] = i; } for (int j = 0; j <= n; j++) { len[0][j] = j; } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (a.charAt(i) == b.charAt(j)) { len[i + 1][j + 1] = len[i][j]; } else { len[i + 1][j + 1] = 1 + Math.min(len[i][j], Math.min(len[i + 1][j], len[i][j + 1])); } } } return len[m][n]; } public static void main(String[] args) { String a = "helloworld"; String b = "owo"; System.out.print("Edit distance between '"+ a +"' and '"+b +"' is "); System.out.print(getEditDistance(a, b)); } }
Output
Edit distance between 'helloworld' and 'owo' is 7
Algorithm Explanation
![]() | Pass arguments to the utility function. |
![]() | Search a path from the start string to the final str. |
![]() | Create a new array with the total length of two strings. |
![]() | Iterate the string and check last char. If last two chars equal, update dp value for +1 length. |
![]() | Return the value and print the string. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
– | O(mn) | – |