Question

what is the time complexity of the edit distance ("ALASKA" vs "ALABAMA" example) dynamic programming algorithm?

what is the space complexity of the edit distance ("ALASKA" vs "ALABAMA" example) dynamic programming algorithm?

Answer 1

Edit Distance Problem Statement :

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character

Solution :
We use dyanamic programming approach where we build a 2-d array of size n x m , where n is length of word1 and m is the length of word2.
dp[i][j] = number of opearions require to convert word1[0...i] to word2[0....j]

if word1[i] == word2[j] then ,
dp[i][j] = dp[i-1][j-1] i.e whatever is the answer till i-1 and j-1
else
dp[i][j] = minium (dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 i.e taking considersation of delete,insert and replace respectively.

ALASKA ALABAMA

in word allaska : we can replace S with B and K with A and add M
Thus , total 3 operations required.

Time Complexity : O(N*M) equivalent to O(N^2) [ using two loops of size N and M]
where N and M are lengths of two words .

Space Complexity : O(N*M) equivalent to O(N^2) [ Using a 2-d array ]

Here's code:

#include <bits/stdc++.h>
using namespace std;
int EditDistance(string word1, string word2) {
int i,j,n,m;
n=word1.size();
m=word2.size();
if(n==0 || m==0)
{
return((n==0)?m:n);
}
vector<vector<int> >dp(n+1,vector<int>(m+1,0)); //declare a 2-d a
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0 && j==0)continue;
if(i==0)
{
dp[i][j]=dp[i][j-1]+1; // we have to insert
}
else if(j==0)
{
dp[i][j]=dp[i-1][j]+1; // we have to delete
}
else if(word1[i-1]==word2[j-1])
{
dp[i][j]=dp[i-1][j-1];
}
else
{
dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) +1; //taking considersation of delete,insert and replace respectively.
}
}
}
return dp[n][m];
}

int main()
{
string s1 = "ALASKA";
string s2 = "ALABAMA";
  
cout<<EditDistance(s1,s2)<<endl;

return 0;
}