public int minDistance(String word1,String word2){

int n1 = word1.length();

int n2 = word2.length();

int[][] dp = new int[n1+1][n2+1];

for (int j = 1; j <=n2 ; j++) {

dp[0][j] = dp[0][j-1] +1;

}

for (int i = 1; i <= n1; i++) {

dp[i][0] = dp[i-1][0] + 1;

}

for (int i = 1; i <=n1 ; i++) {

for (int j = 1; j <=n2 ; j++) {

if (word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];

else dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;

}

}

return dp[n1][n2];

}

public static void main(String[] args) {

String word1 = "horse";

String word2 = "ros";

MinDistance minDistance = new MinDistance();

int r = minDistance.minDistance(word1,word2);

System.out.println(r);

}