Vpropel VIT | POD | 15/05/2020 | Change the word | 06

change_the_word1.cpp

//O(n1*n2)
// Space complexity O(n1*n2)
#include <iostream>
#include<string>
#include<algorithm>
int cword(std::string str1, std::string str2, int n1, int n2) 
{ 
    int l[n1+1][n2+1];
    for (int i = 0; i <= n1; i++) 
    { 
        for (int j = 0; j <= n2; j++) 
        { 
 
            if (i == 0 || j==0) 
                l[i][j] = (i==0)?j:i;
            else
                if (str1[i - 1] == str2[j - 1]) 
                    l[i][j] = l[i - 1][j - 1];
                else
                l[i][j]=1+std::min(std::min(l[i][j-1],l[i-1][j]),l[i-1][j-1]);
                // Insert  Remove Replace 
        } 
    } 
    /*  // To view the List and understand :)
    for(int i=0;i<=n1;i++)
        {
            for(int j=0;j<=n2;j++)
            {
                std::cout<<l[i][j]<<'\t';
            }
            std::cout<<'\n';
        }
    */
    return l[n1][n2]; 
} 
int main() 
{ 
    std::string A; 
    std::string B; 
    std::cin>>A>>B;
    std::cout << cword(A, B, A.size(), B.size()); 
    return 0; 
}
//                                              ### Thank YOu :)
//                                                @cs_jawanda
//                                         .Chiranjeet Singh Jawanda.
//                                                VIT VELLORE

change_the_word2.cpp

//O(3^n)
//Stay away from this approach :-(
// Use DP for the resque :)
#include <iostream>
#include<string>
#include<algorithm>
int cword(std::string str1, std::string str2, int n1, int n2) 
{ 
    if (n1 == 0 || n2==0) 
        return (n1==0)?n2:n1;
    else
        if (str1[n1 - 1] == str2[n2 - 1]) 
            return cword(str1,str2,n1-1,n2-1);
        else
            return 1+std::min(std::min(cword(str1,str2,n1,n2-1),cword(str1,str2,n1-1,n2)),cword(str1,str2,n1-1,n2-1));
            // Insert  Remove Replace 
} 
int main() 
{ 
    std::string A; 
    std::string B; 
    std::cin>>A>>B;
    std::cout << cword(A, B, A.size(), B.size());
    return 0;
} 

change_the_word3.cpp

// O(n1*n2)
// Reducing space complexity to O(n2*2) or O(n2)
#include <iostream>
#include<string>
#include<algorithm>
int cword(std::string str1, std::string str2, int n1, int n2) 
{ 
    int l[2][n2+1]={0};
    for(int i=0;i<=n2;i++)
        l[0][i]=i;
    for (int i = 1; i <= n1; i++) 
    { 
        for (int j = 0; j <= n2; j++) 
        { 
 
            if (j==0) 
                l[i%2][j] =i;
            else
                if (str1[i-1] == str2[j-1])
                    l[i%2][j] = l[(i-1)%2][j-1];
                else
                l[i%2][j]=1+std::min(std::min(l[i%2][j-1],l[(i-1)%2][j]),l[(i-1)%2][j-1]);
                // Insert  Remove Replace 
        } 
    } 
    /*  // To view the List and understand :)
    for(int i=0;i<=n1;i++)
        {
            for(int j=0;j<=n2;j++)
            {
                std::cout<<l[i][j]<<'\t';
            }
            std::cout<<'\n';
        }
    */
    return l[n1%2][n2]; 
} 
int main() 
{ 
    std::string A; 
    std::string B; 
    std::cin>>A>>B;
    std::cout << cword(A, B, A.size(), B.size()); 
    return 0; 
}

Question(change_the_word).txt

Change the word
You’ll be given with two words.You have to convert the first word to second with minimal number of operation.
You can add or delete or replace a character to word1.Find the minimal number of operation.

Example:-

Input: word1 = "intention", word2 = "execution"

Output: 5

Explanation: 

intention -> inention (remove 't')

inention -> enention (replace 'i' with 'e')

enention -> exention (replace 'n' with 'x')

exention -> exection (replace 'n' with 'c')

exection -> execution (insert 'u')


Input format:-

First string

Second string

Output format:-

Minimal  number of operations






------------------------------------------------------------------------------------
// -To clear concept:-
//  https://www.geeksforgeeks.org/edit-distance-dp-5/
//  https://medium.com/@dakota.lillie/an-intro-to-dynamic-programming-pt-ii-edit-distance-ceed0b12fe6d
//  https://www.youtube.com/watch?v=OQ5jsbhAv_M&list=PLfMspJ0TLR5HRFu2kLh3U4mvStMO8QURm