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.