| 8 | using namespace std; |
| 9 | |
| 10 | int editDistance(string str1, string str2, int I, int D, int S) { |
| 11 | // n string 1 lentgth, m string 2 length |
| 12 | int n = str1.length(), m = str2.length(); |
| 13 | |
| 14 | // Creating dp 2D vector to store all possible ways and save the minimum cost using Bottom Up Approach |
| 15 | vector<vector<int>>dp(n + 1, vector<int>(m + 1)); |
| 16 | |
| 17 | // Initializing row 0 with deletion cost as row 0 represents word's characters deletion |
| 18 | for (int i = 0; i <= n; i++) |
| 19 | dp[i][0] = i * D; |
| 20 | |
| 21 | // Initializing column 0 with I cost as column 0 represents word's characters insertion |
| 22 | for (int i = 0; i <= m; i++) |
| 23 | dp[0][i] = i * I; |
| 24 | |
| 25 | // Begin with 1 as row 0 and column 0 are initialized |
| 26 | for (int i = 1; i <= n; i++) { |
| 27 | for (int j = 1; j <= m; j++) { |
| 28 | // If the 2 characters are similar then do nothing by taking the previous diagonal value without adding any cost |
| 29 | if (str1[i - 1] == str2[j - 1]) |
| 30 | dp[i][j] = dp[i - 1][j - 1]; |
| 31 | |
| 32 | /* |
| 33 | If the 2 characters are not similar |
| 34 | then choose the least cost between: inserting new character by taking the previous col plus insertion cost |
| 35 | : deleting the character by taking the previous row plus deletion cost |
| 36 | : substituting the character by taking the previous diagonal value plus substition cost |
| 37 | */ |
| 38 | else |
| 39 | dp[i][j] = min((dp[i - 1][j] + D), min((dp[i][j - 1] + I), (dp[i - 1][j - 1] + S))); |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | // Print the min possible value from the last element in the constructed matrix |
| 44 | return dp[n][m]; |
| 45 | } |
| 46 | |
| 47 | int main() { |
| 48 | |