The idea is closely based on the edit distance problem,

where you end up building the dp array with the following equation:

dp[i][j] represent the solution for the subproblem word1(1..i) and word2(1..j)

dp[i][j] = dp[i-1][j-1] if the word1[i] == word2[j]

= 1 + Math.min(dp[i-1][j], dp[i][j-1]), if not equal

```
public static int minDistance(String word1, String word2) {
int len1 = word1.length()+1, len2 = word2.length()+1;
int[][] dp = new int[len1][len2];
for(int i = 0; i < len1; i++) {
for(int j = 0; j < len2; j++) {
if(i == 0 && j == 0) dp[i][j] = 0;
else if(i == 0) dp[i][j] = 1 + dp[i][j-1];
else if(j == 0) dp[i][j] = 1 + dp[i-1][j];
else if(word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[len1-1][len2-1];
}
```