题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case String s1 = in.nextLine(); String s2 = in.nextLine(); // 当其中一个字符串为空串时,编辑距离为另一字符串长度 // dp[i][j]:s1的前i个字符与s2的前j个字符所需要的编辑距离 int dp[][] = new int[s1.length() + 1][s2.length() + 1]; // 其中一个字符串为空串时初始化 for(int i = 0;i <= s1.length();i++){ dp[i][0] = i; } for(int j = 0;j <= s2.length();j++){ dp[0][j] = j; } for(int i = 1;i <= s1.length();i++){ for(int j = 1;j <= s2.length();j++){ // 状态转移 // 1、当s1的第i个字符与s2的第j个字符相等时。不需要编辑即编辑距离为dp[i -1][j -1] if(s1.charAt(i - 1) == s2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1]; }else{ // 2、当所在对应位置字符不相等时 // 替换字符串b,编辑距离为dp[i-1][j-1]+1 // 插入一个字符与其相等,则编辑距离为dp[i-1][j]+1; // 删除该字符,编辑距离为dp[i][j-1]+1,三者取其小即可 dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1],dp[i - 1][j]),dp[i][j - 1]) + 1; } } } System.out.println(dp[s1.length()][s2.length()]); } } }