题目
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
答案
class Solution {
public int minDistance(String ss1, String ss2) {
int m = ss1.length(), n = ss2.length();
char[] s1 = ss1.toCharArray(), s2 = ss2.toCharArray();
// f[i][j]: What is the minimum edit distance between s1[i...m-1] and s2[j...n-1] ?
int[][] f = new int[m+1][n+1];
// When s[i] == s[j]:
// f[i][j] = f[i+1][j+1] (nothing changed)
// When s[i] != s[j]:
// f[i][j] = f[i+1][j+1] + 1 (replace s[i])
// f[i][j] = f[i + 1][j] + 1 (delete s[i])
// f[i][j] = f[i][j+1] + 1 (insert some char before s[i])
for(int i = m; i >= 0; i--) {
for(int j = n; j >= 0; j--) {
// Base cases
if(i == m) {
f[i][j] = n - j;
continue;
}
if(j == n) {
f[i][j] = m - i;
continue;
}
int a = f[i + 1][j] + 1;
int b = f[i][j + 1] + 1;
int c = (s1[i] == s2[j])? (f[i+1][j+1]) : (f[i+1][j+1] + 1);
f[i][j] = Math.min(a, Math.min(b, c));
}
}
return f[0][0];
}
}
