6. Min Edit Distance [VMWare]

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to…

6. Min Edit Distance [VMWare]

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

  1. Insert
  2. Remove
  3. Replace 
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Problem: https://leetcode.com/problems/edit-distance/

How to approach the solution?

  1. Brute Force O(3m) exponential
a. If last characters of two strings are same, nothing much to do. Ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1.
b. Else (If last characters are not same), we consider all operations on ‘str1’, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values.
Insert: Recur for m and n-1
Remove: Recur for m-1 and n
Replace: Recur for m-1 and n-1

2. Levenstein distance algorithm.

This approach uses DP, no recursion. Time and space complexity O(MN). M and N being length of string 1 and 2 respectively.

Congratulations! You just solved a problem that was asked in interviews at VMWare, Microsoft , Facebook & Google.

Thanks for reading this article, keep learning & growing.

Github: https://github.com/charlieInDen/InterviewQuestions-Swift/