Spoj EDIST Solution

EDIST - Edit distance

#include<bits/stdc++.h>

#define N 1020110

#define ll long long

#define ld long double

#define ull unsigned long long

#define pi pair<int, int>

#define pii pair<ll, int>

#define piii pair<ll, ll>

#define mi map<int, int>

#define mli map<ll, int>

#define mll map<ll, ll>

#define mod 100000007

#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define point cout<<showpoint<<fixed<<setprecision(8);

using namespace std;

int minimum(int a, int b, int c)

{

    return min(a, min(b, c));

}

int main()

{

    fastio

    int t;

    cin >> t;

    while(t--)

    {

        string str1, str2;

        cin >> str1 >> str2;

        int n = str1.size();

        int m = str2.size();

        int dp[n+1][m+1];

        for(int i=0; i<=n; i++)

        {

            for(int j=0; j<=m; j++)

            {

                if(i == 0)

                    dp[i][j] = j;

                else if(j == 0)

                    dp[i][j] = i;

                else if(str1[i-1] == str2[j-1])

                    dp[i][j] = dp[i-1][j-1];

                else

                    dp[i][j] = 1 + minimum(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]);

            }

        }

        cout << dp[n][m] << "\n";

    }

    return 0;

}