Description

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')

Analysis

It is easy to come up with dynamic programming. But what is the optimal substructure?

Initially, I tried to list the table and find the pattern. It doesn’t work and waste me much time. So instead of trying to find the pattern, considering about the process of changing from the substructure to the larger structure is the main point.

Set \(i\) as the length of the word to be changed from and \(j\) as the length of the target word. And \(dp[i][j]\) shows the number of operations.

if \(word1[i]=word2[j]\), obviously, \(dp[i][j]=dp[i-1][j-1]\).

Otherwise, we should insert, delete or replace an element.

If an element is inserted, then \(dp[i][j]=dp[i][j-1]+1\).

If an element is deleted, then \(dp[i][j]=dp[i-1][j]+1\).

If an element is replaced, then \(dp[i][j]=dp[i-1][j-1]\).

We should implement the process that needs the minimum operations.

The time and space are both \(m*n\) where \(m\) and \(n\) are the length of \(word1\) and \(word2\).

Solution

class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length(),n=word2.length();
        int[][] dp=new int[m+1][n+1];
        dp[0][0]=0;
        for(int i=0;i<m;i++)
        {
            dp[i+1][0]=i+1;
        }
        for(int j=0;j<n;j++)
        {
            dp[0][j+1]=j+1;
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(word1.charAt(i)==word2.charAt(j)) dp[i+1][j+1]=dp[i][j];
                else
                {
                    dp[i+1][j+1]=Math.min(Math.min(dp[i+1][j]+1,dp[i][j+1]+1),dp[i][j]+1);
                }
            }
        }
        return dp[m][n];
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/EditDistance.java

 

Leave a Reply

Your email address will not be published. Required fields are marked *