第一行输入一个长度为
,仅由小写字母组成的字符串
。
第二行输入一个长度为
,仅由小写字母组成的字符串
。
输出一个整数,表示
和
的编辑距离。
abcdefg abcdef
1
在这个样例中,可以选择将
末尾的
删除。当然,也可以选择在
末尾插入
。
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str1 = sc.nextLine(); String str2 = sc.nextLine(); int[][] res = new int[str1.length()][str2.length()]; for (int i = 0; i < str1.length(); i++) { for (int j = 0; j < str2.length(); j++) { char c1 = str1.charAt(i); char c2 = str2.charAt(j); if (i == 0) { res[i][j] = str2.substring(0, j + 1).indexOf(c1) >= 0 ? j : j + 1; continue; } if (j == 0) { res[i][j] = str1.substring(0, i + 1).indexOf(c2) >= 0 ? i : i + 1; continue; } if (c1 == c2) { res[i][j] = res[i - 1][j - 1]; } else { int r1 = res[i][j - 1] + 1; int r2 = res[i - 1][j] + 1; int r3 = res[i - 1][j - 1] + 1; res[i][j] = Math.min(r1, Math.min(r2, r3)); } } } System.out.println(res[str1.length() - 1][str2.length() - 1]); } }
package hj; import javax.naming.Name; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @className: _5_2 * @author: Lian * @date: 2023-10-04 11:06 */ public class _5_2 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str1 = br.readLine().toCharArray(); char[] str2 = br.readLine().toCharArray(); int a=str1.length,b=str2.length; int[][] arr=new int[a+1][b+1]; for(int i=0;i<a+1;i++){ for(int j=0;j<b+1;j++){ arr[i][j]=Integer.MAX_VALUE; } } for(int i=0;i<=a;i++){ arr[i][0]=i; } for(int i=0;i<=b;i++){ arr[0][i]=i; } for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ if(str1[i-1]==str2[j-1]){ arr[i][j]=arr[i-1][j-1]; } arr[i][j]=Math.min(arr[i][j],arr[i-1][j]+1); arr[i][j]=Math.min(arr[i][j],arr[i][j-1]+1); arr[i][j]=Math.min(arr[i][j],arr[i-1][j-1]+1); } } System.out.println(arr[a][b]); } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); char[] A=in.nextLine().toCharArray(); char[] B=in.nextLine().toCharArray(); int[][] DP=new int[A.length+1][B.length+1]; DP[0][0]=0; for(int i=0;i<=A.length;i++){ for(int j=0;j<=B.length;j++){ if(i!=0&&j!=0){ DP[i][j]=i+j; DP[i][j]=Math.min(DP[i][j],DP[i-1][j]+1); DP[i][j]=Math.min(DP[i][j],DP[i][j-1]+1); DP[i][j]=Math.min(DP[i][j],DP[i-1][j-1]+(A[i-1]==B[j-1]?0:1)); }else if(i!=0){ DP[i][j]=i; }else if(j!=0){ DP[i][j]=j; } } } System.out.println(DP[A.length][B.length]); } }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String strA = in.nextLine(); String strB = in.nextLine(); System.out.print(getEditDistance(strA,strB)); } public static int getEditDistance(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) { dp[i][0] = i; } for (int j = 0; j <= n; j++) { dp[0][j] = j; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1; } } } return dp[m][n]; } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String stra=br.readLine(); String strb=br.readLine(); int num1=0; int[][] dis=new int[stra.length()+1][strb.length()+1]; for(int i=0;i<=stra.length();i++){ dis[i][0]=i; } for(int i=0;i<=strb.length();i++){ dis[0][i]=i; } for(int i=1;i<=stra.length();i++){ for(int j=1;j<=strb.length();j++){ if(stra.charAt(i-1)==strb.charAt(j-1)){ dis[i][j]=dis[i-1][j-1]; }else{ num1=Math.min(dis[i-1][j],dis[i][j-1]); dis[i][j]=Math.min(num1,dis[i-1][j-1])+1; } } } System.out.println(dis[stra.length()][strb.length()]); } }
import java.util.*; public class Main { //动态规划 public static void main(String[] args){ Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); int len1 = s1.length(),len2 = s2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; //初始化 for(int i = 1;i <= len2;i++) dp[0][i] = i; for(int i = 1;i <= len1;i++) dp[i][0] = i; for(int i = 1;i <= len1;i++){ for(int j = 1;j<= len2;j++){ if(s1.charAt(i - 1) == s2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1]; }else{ //替换 dp[i][j] = dp[i][j] == 0 ? dp[i - 1][j - 1] + 1 : Math.min(dp[i - 1][j - 1] + 1,dp[i][j]); //插入 dp[i][j] = Math.min(dp[i][j - 1] + 1,dp[i][j]); //删除 dp[i][j] = Math.min(dp[i - 1][j] + 1,dp[i][j]); } } } System.out.println(dp[len1][len2]); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[] a = sc.nextLine().toCharArray(); char[] b = sc.nextLine().toCharArray(); int n = a.length, m = b.length; int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i <= m; i++) { dp[0][i] = i; } for (int i = 1; i <= n; i++) { dp[i][0] = i; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1; dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + (a[i - 1] == b[j - 1] ? 0 : 1)); } } System.out.println(dp[n][m]); } }
public static void main(String[] args){ Scanner sc = new Scanner(System.in); String str1 = sc.nextLine(); String str2 = sc.nextLine(); int N = str1.length(); int M = str2.length(); int [][] dp = new int[N][M]; //1 dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 0 : 1; //2 for(int j = 1; j < M; j++){ dp[0][j] = str1.charAt(0) == str2.charAt(j) ? j : dp[0][j-1]+1; } //3 for(int i = 1; i < N; i++){ dp[i][0] = str1.charAt(i) == str2.charAt(0) ? i : dp[i-1][0]+1; } //4 for(int i = 1; i < N; i++){ for(int j = 1; j < M; j++){ int p1 = dp[i-1][j]+1; int p2 = dp[i][j-1]+1; int p3 = str1.charAt(i) == str2.charAt(j) ? dp[i-1][j-1] : dp[i-1][j-1]+1; int min = Math.min(p1, p2); min = Math.min(min, p3); dp[i][j] = min; } } System.out.println(dp[N-1][M-1]); } //暴力递归复杂度高,测试用例一个都过不了 public static int process(String str1, String str2, int i, int j){ //1 if(i == 0 && j == 0) { return str1.charAt(0) == str2.charAt(0) ? 0 : 1; //2 } else if(i == 0){ if(str1.charAt(0) == str2.charAt(j)){ return j; } else { return process(str1, str2, 0, j-1)+1; } //3 } else if(j == 0){ if(str1.charAt(i) == str2.charAt(0)){ return i; } else { return process(str1, str2, i-1, 0)+1; } //4 } else{ int p1 = process( str1, str2, i-1, j)+1; int p2 = process( str1, str2, i, j-1)+1; int p3 = str1.charAt(i) == str2.charAt(j) ? process( str1, str2, i-1, j-1) : process( str1, str2, i-1, j-1)+1; int min = Math.min(p1, p2); min = Math.min(min, p3); return min; } }
import java.util.*; public class Main{ public static int distancefun(String str1,String str2){ int row = str1.length(); int col = str2.length(); int[][] dp = new int[row+1][col+1]; //初始状态:f(i,0) = i; f(0,j) = j; //状态转移: f(i,j) = str[i]==str2[j]? f(i-1,j-1): min(f(i-1,j),f(i,j-1),f(i-1,j-1))+1 //状态定义: f(i,j) str1 前 i 个子串和 str2 前j 个子串的最小编辑距离 //返回结果:f(row,col); for(int i = 0;i<= row;i++){ dp[i][0] = i; } for(int i = 0;i<=col;i++){ dp[0][i] = i; } for(int i = 1;i<=row;i++){ for(int j = 1;j<=col;j++){ if(str1.charAt(i-1)==str2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ int min = Math.min(dp[i-1][j],dp[i][j-1]); dp[i][j] = Math.min(dp[i-1][j-1],min) + 1; } } } return dp[row][col]; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); String str1 = sc.nextLine(); String str2 = sc.nextLine(); int result = distancefun(str1,str2); System.out.println(result); } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String s1 = sc.next(); String s2 = sc.next(); int dp[][] = new int[s1.length()+1][s2.length()+1]; dp[0][0] = 0; for(int i = 1;i<dp.length;i++){ dp[i][0] = i; } for(int i = 1;i<dp[0].length;i++){ dp[0][i] = i; } for(int i = 1;i<dp.length;i++){ for(int j = 1;j<dp[0].length;j++){ if(s1.charAt(i-1)==s2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1)); } } } System.out.println(dp[s1.length()][s2.length()]); } } }
import java.util.*; public class Main{ public static int fun(String s1,String s2){ char[] ch1 = s1.toCharArray(); char[] ch2 = s2.toCharArray(); int len1 = ch1.length; int len2 = ch2.length; int[][] res = new int[len1 + 1][len2 + 1]; //初始化第一行和第一列 for(int i = 0;i <= len1;i++){ res[i][0] = i; } for(int j = 0;j <= len2;j++){ res[0][j] = j; } for(int i = 1;i <= len1;i++){ for(int j = 1;j <= len2;j++){ //求插入和删除的最小值 res[i][j] = Math.min(res[i - 1][j],res[i][j - 1])+1; //和替换进行比较 if(ch1[i - 1] == ch2[j - 1]){ res[i][j] = Math.min(res[i][j],res[i - 1][j - 1]); }else{ res[i][j] = Math.min(res[i][j],res[i - 1][j - 1] + 1); } } } return res[len1][len2]; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String s1 = sc.nextLine(); String s2 = sc.nextLine(); System.out.println( fun(s1,s2)); } } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String str1 = sc.next(); String str2 = sc.next(); System.out.println(distanceString(str1, str2)); } } public static int distanceString(String str1, String str2) { int len1 = str1.length(), len2 = str2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; // 初始化 int i = 0, j = 0; for (i = 0; i <= len1; i++) { dp[i][0] = i; } for (j = 0; j <= len2; j++) { dp[0][j] = j; } // 动态规划,循环设置值 for (i = 1; i <= len1; i++) { for (j = 1; j <= len2; j++) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = minNum(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1; } } } return dp[len1][len2]; } public static int minNum(int num1, int num2, int num3) { int temp = num1 < num2 ? num1 : num2; return temp < num3 ? temp : num3; } }
import java.util.*; public class Main{ public static void main (String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String str1 = sc.nextLine(); String str2 = sc.nextLine(); int[][] dp = new int[str1.length() + 1][str2.length() + 1]; dp[0][0] = 0; for (int i = 0; i <= str1.length(); i++){ for (int j = 0; j <= str2.length(); j++){ if (i == 0) dp[i][j] = j; else if (j == 0) dp[i][j] = i; else if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1; } } System.out.println(dp[str1.length()][str2.length()]); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String str1 = sc.next(); String str2 = sc.next(); System.out.println(distance(str1,str2)); } } public static int distance(String str1,String str2){ int len1 = str1.length(); int len2 = str2.length(); int[][] dp = new int[len1+1][len2+1]; for(int i = 0; i < len1+1;i++){ dp[i][0] = i; } for(int i = 0; i < len2+1;i++){ dp[0][i] = i; } for(int i = 1; i < len1+1;i++){ for(int j = 1; j < len2+1;j++){ if(str1.charAt(i-1)==str2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1)); } } } return dp[len1][len2]; } }
import java.util.Scanner; /** * @author Yuliang.Lee * @version 1.0 * @date 2021/9/23 18:00 * 计算字符串的距离: Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。 编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。 Ex: 字符串A: abcdefg 字符串B: abcdef 通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。 要求:给定任意两个字符串,写出一个算法计算它们的编辑距离。 * 解题思路: 这题考的是levenshtein距离的计算,需要运用动态规划去解决该类问题。 迭代公式: lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离; 插入和删除操作互为逆过程:a删除指定字符变b等同于b插入指定字符变a; 如果a[i] == b[j],则说明a[i]和b[j]分别加入a,b之后不会影响levenshtein距离,lev[i][j] = lev[i-1][j-1] + 0; 如果a[i] != b[j],则需要考虑3种情况的可能: a中插入字符,即lev[i][j] = lev[i-1][j] + 1; b中插入字符,即lev[i][j] = lev[i][j-1] + 1; a[i]替换成b[j],lev[i][j] = lev[i-1][j-1] + 1; 取这3种情况的最小值。 细节补充: 二维数组的初始化以及迭代算法的修正体现在代码实现中。 * 示例: 输入: abcdefg abcdef abcde abcdf abcde bcdef 输出: 1 1 2 */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { String str1 = in.nextLine(); String str2 = in.nextLine(); int len1 = str1.length(); int len2 = str2.length(); int[][] lev = new int[len1][len2]; // 初始化 if (str1.charAt(0) == str2.charAt(0)) { lev[0][0] = 0; } else { lev[0][0] = 1; } // dp填充数组 for (int i = 0; i < len1; i++) { char a = str1.charAt(i); for (int j = 0; j < len2; j++) { char b = str2.charAt(j); if (a == b) { if (i > 0 && j > 0) { lev[i][j] = lev[i-1][j-1]; } } else if (i > 0 || j > 0) { int min = Integer.MAX_VALUE; if (i > 0 && lev[i-1][j] + 1 < min) { min = lev[i-1][j] + 1; } if (j > 0 && lev[i][j-1] + 1 < min) { min = lev[i][j-1] + 1; } if (i > 0 && j > 0 && lev[i-1][j-1] + 1 < min) { min = lev[i-1][j-1] + 1; } lev[i][j] = min; } // 算法校正:levenshtein距离的最小值为两个字符串长度之差 lev[i][j] = lev[i][j] < Math.abs(i - j) ? Math.abs(i - j) : lev[i][j]; } } // 结果输出 System.out.println(lev[len1 - 1][len2 - 1]); } } }
java解法 DP: (1)k1代表替换: 相等 k1 = arr[i-1][i1-1] 不相等 k1 = arr[i-1][i1-1]+1 (2)k2代表删除str1中的这个字符: k2 = arr[i-1][i1] + 1 (3)k3代表增加str2的这个字符到str1中: k3 = arr[i][i1-1] + 1 (4)arr[i][i1-1]取k1,k2,k3的最小值 (5)要先把当i=0或者i1=0时,arr[i][i1]的值先填上 import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner scnner = new Scanner(System.in); while(scnner.hasNext()){ String str1 = scnner.nextLine(); String str2 = scnner.nextLine(); int l1 = str1.length(); int l2 = str2.length(); str1 = " "+ str1; str2 = " "+ str2; int[][] arr = new int[l1+1][l2+1]; //记录最长子字符串 //str1为空时,转换需要的次数 for (int i = 1; i <= l2; i++) { arr[0][i] = i; } //str2为空时,转换需要的次数 for (int i = 1; i <= l1; i++) { arr[i][0] = i; } for (int i = 1; i <= l1; i++) { for (int i1 = 1; i1 <= l2; i1++) { int k1; if(str1.charAt(i) == str2.charAt(i1)){ k1 = arr[i-1][i1-1]; }else{ k1 = arr[i-1][i1-1] + 1; } int k2 = arr[i-1][i1] + 1; //删除str1[i] int k3 = arr[i][i1-1] + 1; //增加str2[i1] arr[i][i1] = Math.min(k1,k2); arr[i][i1] = Math.min(arr[i][i1],k3); } } System.out.println(arr[l1][l2]); } } }