Given two strings, calculate the minimum number of edits required to transform the first string into the second. The allowed operations are:<\/p>\n\n\n\n
dp<\/code> where dp[i][j]<\/code> represents the minimum edit distance between the first i<\/code> characters of string X<\/code> and the first j<\/code> characters of string Y<\/code>.<\/li>\n<\/ol>\n\n\n\nDynamic Programming Approach<\/h3>\n\n\n\n\n- Step 1<\/strong>: Initialize a 2D array
dp<\/code> of size (m+1) x (n+1)<\/code>, where m<\/code> is the length of string X<\/code> and n<\/code> is the length of string Y<\/code>.<\/li>\n\n\n\n- Step 2<\/strong>: Fill the first row and the first column to represent the cost of converting between an empty string and a substring of the other string.<\/li>\n\n\n\n
- Step 3<\/strong>: Iterate through each character of both strings to fill the
dp<\/code> table based on the minimum operations required.<\/li>\n<\/ul>\n\n\n\nC Program for Minimum Edit Distance<\/h3>\n\n\n\n
Here\u2019s a complete C program to compute the Minimum Edit Distance:<\/p>\n\n\n
\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\n\/\/ Function to calculate the minimum edit distance\nint minEditDistance(char* X, char* Y) {\n int m = strlen(X);\n int n = strlen(Y);\n \n \/\/ Create a DP table\n int** dp = (int**)malloc((m + 1) * sizeof(int*));\n for (int i = 0; i <= m; i++) {\n dp[i] = (int*)malloc((n + 1) * sizeof(int));\n }\n\n \/\/ Initialize the first row and column\n for (int i = 0; i <= m; i++) {\n dp[i][0] = i; \/\/ Deletion cost\n }\n for (int j = 0; j <= n; j++) {\n dp[0][j] = j; \/\/ Insertion cost\n }\n\n \/\/ Fill the DP table\n for (int i = 1; i <= m; i++) {\n for (int j = 1; j <= n; j++) {\n if (X[i - 1] == Y[j - 1]) {\n dp[i][j] = dp[i - 1][j - 1]; \/\/ No operation needed\n } else {\n dp[i][j] = 1 + (dp[i - 1][j - 1] < dp[i][j - 1] ? \n (dp[i - 1][j - 1] < dp[i][j - 1] ? \n dp[i - 1][j - 1] : dp[i][j - 1]) : \n (dp[i][j - 1] < dp[i - 1][j] ? \n dp[i][j - 1] : dp[i - 1][j]));\n }\n }\n }\n\n \/\/ The minimum edit distance is in dp[m][n]\n int distance = dp[m][n];\n\n \/\/ Free the allocated memory\n for (int i = 0; i <= m; i++) {\n free(dp[i]);\n }\n free(dp);\n\n return distance;\n}\n\n\/\/ Main function\nint main() {\n char X[100], Y[100];\n\n \/\/ Input the two strings\n printf("Enter first string: ");\n fgets(X, sizeof(X), stdin);\n X[strcspn(X, "\\n")] = '\\0'; \/\/ Remove newline character\n\n printf("Enter second string: ");\n fgets(Y, sizeof(Y), stdin);\n Y[strcspn(Y, "\\n")] = '\\0'; \/\/ Remove newline character\n\n \/\/ Calculate the minimum edit distance\n int distance = minEditDistance(X, Y);\n printf("Minimum Edit Distance (Levenshtein Distance): %d\\n", distance);\n\n return 0;\n}\n\n<\/pre><\/div>\n\n\nExplanation of the Code<\/h3>\n\n\n\n\n- Dynamic Programming Table<\/strong>:\n
\n- A 2D array
dp<\/code> is created, where dp[i][j]<\/code> holds the minimum edit distance between the first i<\/code> characters of string X<\/code> and the first j<\/code> characters of string Y<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Initialization<\/strong>:\n
\n- The first row represents the cost of converting from an empty string to substrings of
Y<\/code>, which is equal to the length of those substrings (insertion cost).<\/li>\n\n\n\n- The first column represents the cost of converting from substrings of
X<\/code> to an empty string, which is equal to the length of those substrings (deletion cost).<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Filling the DP Table<\/strong>:\n
\n- We iterate through both strings, checking if the characters match. If they do, no additional cost is incurred. If they don\u2019t, we compute the minimum cost of the three possible operations (insertion, deletion, substitution).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Memory Management<\/strong>:\n
\n- The program dynamically allocates memory for the
dp<\/code> array and frees it after use to prevent memory leaks.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\nInput and Output Example<\/h3>\n\n\n\nInput<\/h4>\n\n\n\ncCopy codeEnter first string:kitten\nEnter second string:sitting\n<\/code><\/pre>\n\n\n\nOutput<\/h4>\n\n\n\njavaCopy codeMinimum Edit Distance (Levenshtein Distance): 3\n<\/code><\/pre>\n\n\n\nExplanation of the Output<\/h3>\n\n\n\n
In this case, the minimum edit distance of 3<\/code> can be achieved by:<\/p>\n\n\n\n\n- Substituting ‘k’ with ‘s’<\/li>\n\n\n\n
- Substituting ‘e’ with ‘i’<\/li>\n\n\n\n
- Inserting ‘g’ at the end.<\/li>\n<\/ol>\n\n\n\n
Conclusion<\/h3>\n\n\n\n
This C program efficiently computes the Minimum Edit Distance (Levenshtein Distance) between two strings using dynamic programming. It allows user input for flexibility and outputs the minimum number of edits required to convert one string into another. You can test various pairs of strings to see how the edit distance changes, making this approach useful in various applications, including spell checking, DNA sequence analysis, and more.<\/p>\n