Edit Distance – LeetCode Solution [Hard]

Problem statement

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 three following 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 [LeetCode]

Leave a Reply