Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (each operation is counted as 1 step.)
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
}
else if (j == 0) {
dp[i][j] = i;
}
else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
int replace = dp[i - 1][j - 1] + 1;
// insert word2.charAt(j - 1) into word1
int insert = dp[i][j - 1] + 1;
// delete word1.charAt(i - 1)
int delete = dp[i - 1][j] + 1;
dp[i][j] = Math.min(replace, Math.min(insert, delete));
}
}
}
return dp[m][n];
}
}