Problem
Given two strings word1 and word2 (in lowercase alphabets), return the minimum number of operations required to convert word1 to word2.
You could only perform following three operations on a word:
- Insert a character
- Delete a character
- Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Edit Distance Solution
Pseudocode (Bottom up)
1. Traverse both strings from left to right
2. Do:
if current characters of two strings are equal, do nothing and traverse for remaining string ie dp[i][j] = dp[i-1][j-1]
if current characters are not equal, consider any of the three operations:
1- Insert: Recur for m and n-1: dp[i][j-1]
2- Remove: Recur for m-1 and n: dp[i-1][j]
3- Replace: Recur for m-1 and n-1: dp[i-1][j-1]
3. And take minimum of the three + 1(for the operation)
Code Implementation
//
// main.cpp
// Edit Distance
//
// Created by Himanshu on 16/09/21.
//
#include <iostream>
#include <string>
using namespace std;
int solve (string s1, string s2) {
int n = (int) s1.length(), m = (int) s2.length();
int dp[n+1][m+1];
for (int i=0; i<=n; i++) {
for (int j=0; j<=m; j++) {
dp[i][j] = 0;
}
}
for (int i=0; i<=n; i++) {
dp[i][0] = i;
}
for (int j=0; j<=m; j++) {
dp[0][j] = j;
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
else {
dp[i][j] = 1 + min((min(dp[i-1][j],
dp[i][j-1])),
dp[i-1][j-1]);
}
}
}
return dp[n][m];
}
int main() {
string s1 = "hello", s2 = "tell";
cout<<solve(s1, s2)<<endl;
return 0;
}
Here’s a working example: Ideone
Practice Problem
Edit Distance