Last active
July 24, 2020 09:59
-
-
Save rahularity/a160be70569e465499a7091d2df75734 to your computer and use it in GitHub Desktop.
Midnight Code: learn before you sleep. (Day 2)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Given two words Word1 and Word2 find 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 | |
| */ | |
| // minimum of three numbers | |
| int min(int x, int y, int z) | |
| { | |
| return min(min(x, y), z); | |
| } | |
| int EditDistance( string word1, int len1, string word2, int len2 ) { | |
| //base case | |
| if(len1 == 0) | |
| return len2; | |
| if(len2 == 0) | |
| return len1; | |
| if( word1[len1-1] == word2[len2-1] ){ | |
| return EditDistance( word1, len1-1, word2, len2-1 ); | |
| } | |
| return 1 + min( EditDistance( word1, len1, word2, len2-1 ), // Insert | |
| EditDistance( word1, len1-1, word2, len2 ), // Delete | |
| EditDistance( word1, len1-1, word2, len2-1) // Replace | |
| ); | |
| } | |
| int main(){ | |
| string word1, word2; | |
| cin >> word1 >> word2; | |
| cout << EditDistance( word1, word1.length(), word2, word2.length() ); | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| ======================EDIT DISTANCE (DYNAMIC PROGRAMMING SOLUTION)====================== | |
| Given two words Word1 and Word2 find 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 | |
| */ | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| //minimum of three numbers | |
| int min(int x, int y, int z) | |
| { | |
| return min(min(x, y), z); | |
| } | |
| int EditDistance( string word1, int len1, string word2, int len2, int** dp ) { | |
| // if already computed then return the answer directly. | |
| if( dp[len1][len2] != -1 ) | |
| return dp[len1][len2]; | |
| //base cases | |
| if(len1 == 0) | |
| return len2; | |
| if(len2 == 0) | |
| return len1; | |
| if( word1[len1-1] == word2[len2-1] ){ | |
| dp[len1][len2] = EditDistance( word1, len1-1, word2, len2-1, dp ); | |
| return dp[len1][len2]; | |
| } | |
| dp[len1][len2] = 1 + min( EditDistance( word1, len1, word2, len2-1, dp ), // Insert | |
| EditDistance( word1, len1-1, word2, len2, dp ), // Delete | |
| EditDistance( word1, len1-1, word2, len2-1, dp) // Replace | |
| ); | |
| return dp[len1][len2]; | |
| } | |
| int main(){ | |
| string word1, word2; | |
| cin >> word1 >> word2; | |
| int len1 = word1.length(); | |
| int len2 = word2.length(); | |
| // making a dp array to store calculated cases. | |
| int** dp = new int*[len1+1]; | |
| // initializing the dp array with -1 | |
| for(int i=0 ; i<=len1 ; i++){ | |
| dp[i] = new int[len2+1]; | |
| for(int j=0 ; j<=len2 ; j++) | |
| dp[i][j] = -1; | |
| } | |
| cout << EditDistance( word1, word1.length(), word2, word2.length(), dp ); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment