edit distance Algorithm
The edit distance algorithm, also known as the Levenshtein distance, is a measure of similarity between two strings or sequences. It is defined as the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. This algorithm is widely used in various applications, including spell checking, DNA sequence alignment, and natural language processing, as it provides a quantitative way to compare and analyze the differences between two strings.
The algorithm's core idea is to use dynamic programming to build a matrix that represents the edit distances between each pair of characters in the input strings. The matrix is initialized with the base case values, where the edit distance between an empty string and a non-empty string is equal to the length of the non-empty string. Then, the algorithm iteratively fills the matrix by comparing the characters in the input strings and updating the corresponding edit distances. The final edit distance between the two strings is found in the bottom right cell of the matrix. By tracing back the path that led to this value, we can also recover the specific edit operations that transform one string into the other.
//
// A Dynamic Programming based C++ program to find minimum
// number operations to convert str1 to str2
//
// The All ▲lgorithms library for python
//
// https://allalgorithms.com/dynamic-programming/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Carlos Abraham
// Github: @abranhe
//
#include<bits/stdc++.h>
using namespace std;
// Utility function to find the minimum of three numbers
int min(int x, int y, int z)
{
return min(min(x, y), z);
}
int editDistDP(string str1, string str2, int m, int n)
{
// Create a table to store results of subproblems
int dp[m+1][n+1];
// Fill d[][] in bottom up manner
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
// If first string is empty, only option is to
// isnert all characters of second string
if (i==0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of second string
else if (j==0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last char
// and recur for remaining string
else if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1];
// If the last character is different, consider all
// possibilities and find the minimum
else
dp[i][j] = 1 + min(dp[i][j-1], // Insert
dp[i-1][j], // Remove
dp[i-1][j-1]); // Replace
}
}
return dp[m][n];
}
// Driver program
int main()
{
// your code goes here
string str1 = "sunday";
string str2 = "saturday";
cout << editDistDP(str1, str2, str1.length(), str2.length());
return 0;
}
