# Edit Distance – LeetCode Solution [Hard]

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: 3Explanation: 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] = i;
}

for (int j=0; j<=m; j++) {
dp[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