Problem description:

Given two strings A and B, find the minimum number of operations needed to transform A into B, there are only three valid operations:

-Replace a character
-Delete a character
-Insert a character

Examples:

A = “hello”
B = “hola”
result = 3, the operations were:
1.- replace ‘e’ with ‘o’   -> “hollo”
2.- replace ‘l’ with ‘a’   -> “holao”
3.- remove ‘o’             -> “hola”

Solution:

So for this problem we have two strings A and B, let’s work with the following example:

A = "abc"
     i
B = "cba"
     j

Remember that we want to transform A into B, any operation has to be done over A.

We are gonna use indexes i and j to loop through the strings and compare them character by character so that at every step we have the following options:

First index i and index j are both at position 0, so we have ‘a’ and ‘c’, since they are different we have three options here:
1.- remove ‘a’ (i + 1,  j)               -> “bc”
2.- insert ‘c’ into A (i, j + 1)         -> “cabc”
3.- replace ‘a’ with ‘c’ (i + 1, j + 1) -> “cbc”

Why don’t we just try them all?

int minDistance(String word1, String word2) {
    int dp[][] = new int[word1.length() + 1][word2.length() + 1];
    for(int i = 0; i <= word1.length(); ++i)
        for(int j = 0; j <= word2.length(); ++j)
            dp[i][j] = -1;
    return getDistance(word1, word2, word1.length(), word2.length(), dp);
}
int getDistance(String word1, String word2, int i, int j, int [][]dp) {
    if(i == 0) return j;
    if(j == 0) return i;
    if(dp[i][j] >= 0) return dp[i][j];

    if(word1.charAt(i - 1) == word2.charAt(j - 1))
        return dp[i][j] = getDistance(word1, word2, i - 1, j - 1, dp);
    else
        return dp[i][j] = 1 + Math.min(getDistance(word1, word2, i - 1, j - 1, dp),
        Math.min(getDistance(word1, word2, i - 1, j, dp), getDistance(word1, word2, i, j - 1, dp)));
 }

The dp table is very important in this problem, it is used to avoid a sub task to be computed more than once, otherwise our program would run very very slow.