05 August 2008
f[i][j] 代表考虑 s1 的前 i 个字符、考虑 s2 的前 j 个字符（但最长公共子序列中不一定包含 s1[i] 或者 s2[j]）时形成的「最长公共子序列（LCS）」长度。
s1[i]==s2[j] : f[i][j]=f[i−1][j−1]+1。代表 必然使用 s1[i] 与 s2[j] 时 LCS 的长度。
s1[i]!=s2[j] : f[i][j]=max(f[i-1][j], f[i][j-1])。代表 必然不使用 s1[i]s1[i]（但可能使用s2[j]）时 和 必然不使用 s2[j]（但可能使用s1[i]）时 LCS 的长度。
时间和空间 O(n * m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int minDistance(String s1, String s2) {
char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
int n = s1.length(), m = s2.length();
int[][] f = new int[n + 1][m + 1];
// 假定存在哨兵空格，初始化 f[0][x] 和 f[x][0]
for (int i = 0; i <= n; i++) f[i][0] = 1;
for (int j = 0; j <= m; j++) f[0][j] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
if (cs1[i - 1] == cs2[j - 1]) f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
}
}
int max = f[n][m] - 1; // 减去哨兵空格
return n - max + m - max;
}
}
定义 f[i][j] 代表考虑 s1 的前 i 个字符、考虑 s2 的前 j 个字符（最终字符串不一定包含 s1[i] 或 s2[j]）时形成相同字符串的最小删除次数。
同理，不失一般性的考虑 f[i][j] 该如何计算：
s1[i]==s2[j]：f[i][j] = f[i - 1][j - 1]，代表可以不用必然删掉 s1[i] 和 s2[j] 形成相同字符串；
f[i][j]=min(f[i−1][j]+1,f[i][j−1]+1)，代表至少一个删除 s1[i] 和 s2[j] 中的其中一个。
f[i][j] 为上述方案中的最小值，最终答案为 f[n][m]。
时间和空间 O(n * m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int minDistance(String s1, String s2) {
char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
int n = s1.length(), m = s2.length();
int[][] f = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) f[i][0] = i;
for (int j = 0; j <= m; j++) f[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (cs1[i - 1] == cs2[j - 1]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
}
}
return f[n][m];
}
}