Saturday, February 22, 2020

Leetcode solution 72. Edit Distance

Problem Statement 

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
  1. Insert a character
  2. Delete a character
  3. 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')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Brute force sounds like really overkill because we have to list all the possible ways and it is exponential time complexity. On a high level, the recursion looks like
  • if cannot convert A to B, return -1 (the recursion termination function); if A == B, then return 0
  • try 3 different ways, insert, remove and replace, cut that character and continue the recursion. Compare the minimum of that 3 methods (exclude -1)
Edit distance is a classic Dynamic Programming (DP) problem, just like Coin Change Problem. It follows the DP template perfectly (asking for extreme values)



The mathematical induction function is
DP[i][j] is the minimum operations needed to convert String[0-i] to String[0-j]
Initial values: dp[0][j] = j and dp[i][0] = i
If (A[i] == B[j]) dp[i][j] =  dp[i-1][j-1]  
Else min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) +1;

Solutions

DP

Time Complexity: O(M*N) where M is word1 length and N is word2 length
Space Complexity: O(M*N) since we need an extra 2D array

References

No comments:

Post a Comment

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!