Sure! Below is the C++ implementation of the Edit Distance problem using dynamic programming: ```cpp #include #include #include #include using namespace std; int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); // Create a 2D DP array vector> dp(m + 1, vector(n + 1, 0)); // Initialize the DP array for (int i = 0; i <= m; ++i) { dp[i][0] = i; } for (int j = 0; j <= n; ++j) { dp[0][j] = j; } // Fill the DP array for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min({dp[i - 1][j] + 1, // Delete dp[i][j - 1] + 1, // Insert dp[i - 1][j - 1] + 1}); // Replace } } } return dp[m][n]; } int main() { string word1 = "horse"; string word2 = "ros"; cout << "Minimum operations to convert '" << word1 << "' to '" << word2 << "': " << minDistance(word1, word2) << endl; word1 = "intention"; word2 = "execution"; cout << "Minimum operations to convert '" << word1 << "' to '" << word2 << "': " << minDistance(word1, word2) << endl; return 0; } ``` ### Explanation of the Code 1. **Initialization**: We initialize a 2D vector `dp` with dimensions `(m+1) x (n+1)` where `m` and `n` are the lengths of `word1` and `word2`, respectively. 2. **Base Cases**: We fill the first row and the first column to handle the cases where one of the strings is empty. 3. **DP Table Filling**: We iterate through each character of both strings and fill the `dp` table based on the rules mentioned above. 4. **Result**: The final answer is found at `dp[m][n]`. ### How to Compile and Run 1. Save the code in a file, for example, `edit_distance.cpp`. 2. Open a terminal and navigate to the directory where the file is saved. 3. Compile the code using a C++ compiler, for example: ```sh g++ -o edit_distance edit_distance.cpp ``` 4. Run the compiled program: ```sh ./edit_distance ``` This will output the minimum number of operations required to convert `word1` to `word2` for the given examples.