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

- A basic DP problem, use the exact same approach as in Unique Path.
- 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