题解 | 计算字符串的编辑距离
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()) { String firstStr = scanner.nextLine(); String secondStr = scanner.nextLine(); int firstLength = firstStr.length(); int secondLength = secondStr.length(); int[][] dp = new int[firstLength + 1][secondLength + 1]; dp[0][0] = 0; //secondStr只有0个字符时,初始化从secondStr变为firstStr时需要的最少的编辑次数,通过添加的形式 for(int i = 1;i <= firstLength; i ++) { dp[i][0] = i; } //firstStr只有0个字符时,初始化从secondStr变为firstStr时需要的最少的编辑次数,通过删除的形式 for(int j = 1;j <= secondLength; j ++) { dp[0][j] = j; } //因为至少有1个字符,所以从下标1开始 for(int i = 1; i <= firstLength; i ++) { for(int j = 1; j <= secondLength; j ++) { //情形1:firstStr有i-1个字符,secondStr有j个字符,转为一样需要的最小编辑次数为dp[i - 1][j], //为什么要加1? firstStr现在为i个字符,secondStr为j个字符,转为一样可以有如下方法(不管哪一种操作,需要的编辑次数都为1) // 1. firstStr去掉第i个字符,编辑次数为1 // 2. secondStr添加第i个字符,编辑次数为1 int val1 = dp[i - 1][j] + 1; int val2 = dp[i][j - 1] + 1; int val3 = dp[i - 1][j - 1]; //比较firstStr的第i个字符和secondStr的第j个字符是否相等,请注意下标(i-1)才是第i个字符 if(!(firstStr.charAt(i - 1) == secondStr.charAt(j - 1))) { val3 = val3 + 1; } //取val1,val2,val3三者最小值,即:firstStr有i个字符,secondeStr有j个字符,它们转为相同时所需要的最小编辑次数 dp[i][j] = Math.min(Math.min(val1,val2),val3); } } System.out.println(dp[firstLength][secondLength]); } } }