EDIST - Edit distance

Edit distance

Given below code is for edist spoj or edit distance spoj .

Hint:-> Standerd edit distance problem you can read it from wikipidea.

1-> Using O(nm) space (n & m are size of strings )

#include <bits/stdc++.h>
using namespace std;
int dp[3000][3000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        char s[3000],t[3000];
        scanf("%s",s);
        scanf("%s",t);
        int size1=strlen(s),size2 = strlen(t);
        memset(dp,0,sizeof(dp[0][0])*(size1+1)*(size2+1));
        for(int i=0;i<=size1;i++)
            dp[i][0] = i;
        for(int j=0;j<=size2;j++)
            dp[0][j] = j;
        for(int i=1;i<=size1;i++)
        {
            for(int j = 1;j<=size2;j++)
            {
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                    dp[i][j] = min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));
            }
        }
        printf("%d\n",dp[size1][size2]);
    }
    return 0;
}

2-> Using O(n) space (n is size of strings )

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        char s[3000],t[3000];
        scanf("%s",s);
        scanf("%s",t);
        int sizes = strlen(s),sizet = strlen(t);
        vector<int> v1(sizet+9),v2(sizet+9);
        for(int i=0;i<=sizet;i++)
            v1[i] = i;
        for(int i=0;i<sizes;i++)
        {
            v2[0] = i+1;
            for(int j=0;j<sizet;j++)
            {
                int add;
                if(s[i] == t[j])
                    add = 0;
                else 
                    add = 1;
                v2[j+1] = min(v2[j]+1,min(v1[j+1]+1,v1[j]+add));
            }
            for(int i=0;i<sizet;i++)
                v1[i] = v2[i];
        }
        printf("%d\n",v2[sizet]);
    }
    return 0;
}