AcWing 902. 最短编辑距离——Java版代码
原题链接
简单
作者:
yqh
,
2020-12-23 16:22:23
,
所有人可见
,
阅读 380
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
char[] tmp;
int n = Integer.parseInt(reader.readLine());
char[] a = new char[n+1];
tmp = reader.readLine().toCharArray();
for (int i = 1; i <= n; i++) {
a[i] = tmp[i-1];
}
int m = Integer.parseInt(reader.readLine());
char[] b = new char[m+1];
tmp = reader.readLine().toCharArray();
for (int i = 1; i <= m; i++) {
b[i] = tmp[i-1];
}
int[][] f = new int[n+1][m+1];
//初始化边界,当a字符串长度为0时,操作次数只和b的长度有关,且只能增加a的长度
for (int i = 0; i <= m; i++) {
f[0][i] = i;
}
//初始化边界,当b字符串长度为0时,操作次数只和a的长度有关,且只能删除a的长度
for (int i = 0; i <= n; i++) {
f[i][0] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//这两种情况是删除与插入对应的情况
//当需要在a上增加一位时,意味着a[1~i]与b[i~j-1]匹配,增加一位b[j]到a上
//则方案数为f[i][j-1]
//当需要在a上删除一位时,意味着a[1~i-1]与b[i~j]匹配,从a上删除一位
//则方案数为f[i-1][j]
f[i][j] = Math.min(f[i-1][j]+1, f[i][j-1]+1);
if (a[i] == b[j]){
//这里是将前面两种操作与不进行操作进行比较
f[i][j] = Math.min(f[i-1][j-1], f[i][j]);
}else{
//这种情况是在最后一位不相同的情况下,将前面两种操作与在a[1~i-1]和b[1~j-1]
//匹配的情况下加上将a[i]替换成b[j]的操作数进行比较
f[i][j] = Math.min(f[i-1][j-1]+1, f[i][j]);
}
}
}
System.out.println(f[n][m]);
}
}