### 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:

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

**Example 2:**

Input:word1 = "intention", word2 = "execution"Output:5Explanation: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