Leetcode–Edit Distance

The Problem:

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

Notes:

  1. A basic DP problem, use the exact same approach as in Unique Path.
  2. Note that the index in the DP array is shifted.

Java Solution

public class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        if(n1==0) return n2;
        if(n2==0) return n1;
        
        int[][] dist = new int[n1+1][n2+1];
        // so here index 0 for dist means zero character, not first character
        for(int i = 0; i <= n1; i++){
            for(int j = 0; j<= n2; j++){
                if(i==0 && j==0)
                    dist[i][j] = 0;
                else if(i==0)
                    dist[i][j] = j;
                else if(j==0)
                    dist[i][j] = i;
                else{
                    int d=0;
                    if(word1.charAt(i-1)!=word2.charAt(j-1)){
                        d = 1;
                    }
                    // from i-1, j-1 by replace or no extra step
                    // from i-1, j by insert
                    // from i, j-1 by delete
                    dist[i][j] =  Math.min(Math.min(dist[i-1][j]+1, dist[i-1][j-1]+d),dist[i][j-1]+1);
                }               
            }
        }
        return dist[n1][n2];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s