Leetcode: Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution:

We can use dynamic programming storing in a matrix how many steps are needed to get from word1.substring(0,i) to word2.substring(0,j). Then the element i,j can be calculated as follows: 

$M(i,j) = min( M(i-1,j) +1, M(i,j-1) +1, M(i-1,j-1)+ C)$, 

where $C= \begin{cases}  0 & \text{if word1[i]==word2[j]} \\ 1 & \text{in other case}\end{cases}$.

public class Solution {

    public int minDistance(String word1, String word2) {

        if(word1.length()==0)

            return word2.length();

        if(word2.length()==0)

            return word1.length();

        int[][] steps = new int[word1.length()+1][word2.length()+1];

        for(int i=0; i<=word1.length(); i++)

            steps[i][0]=i;

        for(int j=0; j<=word2.length(); j++)

            steps[0][j]=j;

        for(int j=1; j<=word2.length(); j++)

        {

            for(int i=1; i<=word1.length(); i++)

            {

                steps[i][j] = steps[i-1][j]<steps[i][j-1] ? steps[i-1][j] +1 : steps[i][j-1]+1; //Adding a letter

                if(word1.charAt(i-1) == word2.charAt(j-1))

                    steps[i][j] = steps[i][j] > steps[i-1][j-1] ? steps[i-1][j-1] : steps[i][j];

                else

                    steps[i][j] = steps[i][j] > steps[i-1][j-1]+1 ? steps[i-1][j-1]+1 : steps[i][j];

            }

                

        }

        return steps[word1.length()][word2.length()];

    }

}