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.
Write a program to find the minimum edit distance between two strings.
Algorithm Explanation
![]() | Pass two strings to the utility function. |
![]() | Create new array using the total length of two strings. |
![]() | Iterate the string and check last char. If last two chars equal, update the value with +1 length |
![]() | Return the value and print the string. |
Source Code
package com.dsacode.DataStructre.array; public class EditDistance { public int minDistance(String word1, String word2) { int len1 = word1.length(); int len2 = word2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 0; i <= len1; i++) { dp[i][0] = i; } for (int j = 0; j <= len2; j++) { dp[0][j] = j; } for (int i = 0; i < len1; i++) { char c1 = word1.charAt(i); for (int j = 0; j < len2; j++) { char c2 = word2.charAt(j); if (c1 == c2) { dp[i + 1][j + 1] = dp[i][j]; } else { int replace = dp[i][j] + 1; int insert = dp[i][j + 1] + 1; int delete = dp[i + 1][j] + 1; int min = replace > insert ? insert : replace; min = delete > min ? min : delete; dp[i + 1][j + 1] = min; } } } return dp[len1][len2]; } public static void main(String[] args) { String str = "Hello world"; String dis= "world"; EditDistance e = new EditDistance(); System.out.println("Minimum distance between '"+ str +"' and '"+ dis +"' : "+e.minDistance(str,dis)); } }
Output
Minimum distance between 'Hello world' and 'world' : 6