/**

class Solution {

public int minDistance(String word1, String word2) {

int[][] dp = new int[word1.length() + 1][word2.length() + 1];

for (int i = 0; i < word1.length() + 1; i++) {

dp[i][0] = i;

}

for (int j = 0; j < word2.length() + 1; j++) {

dp[0][j] = j;

}

for (int m = 1; m < word1.length() + 1; m++) {

for (int n = 1; n < word2.length() + 1; n++) {

if (word1.charAt(m - 1) == word2.charAt(n - 1)) {

dp[m][n] = dp[m - 1][n - 1];

} else {

dp[m][n] = Math.min(dp[m - 1][n - 1], Math.min(dp[m][n - 1], dp[m - 1][n])) + 1;

}

}

}

return dp[word1.length()][word2.length()];

}

}