[编程题]计算字符串的编辑距离
- 热度指数：156391 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行输入一个长度为
，仅由小写字母组成的字符串
。
，仅由小写字母组成的字符串
。
输出描述:
示例1
输入
abcdefg abcdef
输出
1
说明
删除。当然，也可以选择在
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;
}
}
发表于 2021-12-08 15:45:02
回复(0)
动态规划解题
有两个字符串s1[0...m-1]和s2[0...n-1]。s1转换为s2的最后一步有三种情况：
1、假设s1[0...m-2] 已转为为s2[0...n-1]，最小距离为a。那么最后一步就是，s1[0...m-1] 删除末尾一个字符，就得到s2[0...n-1]；等价于，s2[0...n-1]末尾插入一个字符得到s1[0...m-1] 。
2、假设s1[0...m-1] 已转为为s2[0...n-2]，最小距离为b。那么最后一步就是，s1[0...m-1] 末尾插入一个字符，就得到s2[0...n-1]；等价于，s2[0...n-2]删除末尾一个字符得到s1[0...m-1] 。
3、假设s1[0...m-2] 已转为为s2[0...n-2]，最小距离为c。那么最后一步就是，s1[0...m-1] 末尾替换一个字符，得到s2[0...n-1]；等价于，s2[0...n-1]末尾替换一个字符得到s1[0...m-1] 。
那么，s1[0...m-1]转换为s2[0...n-1] 的最小距离为：min(a+1, b+1, c)或min(a+1, b+1, c+1)。
若s1[m - 1] == s2[n - 1] 那么就是min(a+1, b+1, c);
若s1[m - 1] != s2[n - 1] 那么就是min(a+1, b+1, c+1).
以上这三种情况，又可以各自在分三种情况；以此类推，问题可以不断划分为一个个子问题。
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution{
public:
int minDistance(string &s1, string &s2){
int len1 = s1.size(), len2 = s2.size();
if(len1 * len2 == 0)
return 0;
vector<int> dp(len2 + 1, 0);
for(int i = 0, left_up; i < len1 + 1; ++i){
for(int j = 0; j < len2 + 1; ++j){
if(0 == i) dp[j] = j;
else if(0 == j){
left_up = dp[j];
++dp[j];
}else{
if(s1[i - 1] != s2[j - 1]) ++left_up;
left_up = min(min(left_up, dp[j - 1] + 1), dp[j] + 1);
swap(left_up, dp[j]);
}
}
}
return dp[len2];
}
};
int main(){
Solution sol;
string s1, s2;
while(getline(cin, s1) && getline(cin, s2))
cout << sol.minDistance(s1, s2) << endl;
return 0;
} 上面是用一维动态数组。下面是是对应二维动态数组版本的。#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution{
public:
int minDistance(string &s1, string &s2){
int len1 = s1.size(), len2 = s2.size();
if(len1 * len2 == 0)
return 0;
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for(int i = 0; i < len1 + 1; ++i){
for(int j = 0; j < len2 + 1; ++j){
if(0 == i) dp[i][j] = j;
else if(0 == j) dp[i][j] = i;
else{
if(s1[i] != s2[j])
dp[i][j] = min(min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1), dp[i][j - 1] + 1);
else
dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j] + 1), dp[i][j - 1] + 1);
}
}
}
return dp[len1][len2];
}
};
int main(){
Solution sol;
string s1, s2;
while(getline(cin, s1) && getline(cin, s2))
cout << sol.minDistance(s1, s2) << endl;
return 0;
}
发表于 2021-10-22 21:19:06
回复(0)
#include<stdio.h>
#define len 500
int getmin(int a, int b, int c) {
if(a <= b && a <= c) {
return a;
} else if (b <= a && b <= c) {
return b;
} else if (c <= a && c <= b) {
return c;
} else {
return -1;
}
}
int getLev(char a[len], char b[len]) {
int m = strlen(a);
int n = strlen(b);
int cost = 0, lev[len][len] = {0};
for(int i = 0; i <= m; i++) {
lev[i][0] = i;
}
for(int j = 0; j <= n; j++) {
lev[0][j] = j;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(a[i-1] == b[j-1]) {
lev[i][j] = lev[i-1][j-1];
} else {
lev[i][j] = getmin(lev[i][j-1] + 1, lev[i-1][j] + 1, lev[i-1][j-1] + 1);
}
}
}
return lev[m][n];
}
int main() {
char a[len] = {0};
char b[len] = {0};
while(gets(a) && gets(b)) {
printf("%d\n", getLev(a,b));
}
}
发表于 2021-08-17 23:18:46
回复(0)
/*
如何计算编辑距离:
1.两字字串都为空，编辑距离为0
2.当其中一个为空时，编辑距离为另外一个字串的长度。
3.当两个字串非空时（长度分别为i 和 j时），取下面3种情况最小值：
3.1 当i-1 和 j的编辑距离已知时，直接+1 为 i和j的编辑距离
3.2 当i 和 j-1的编辑距离已知时，直接+1 为 i和j的编辑距离
3.3 当i-1 和 j-1的编辑距离已知时，如果i字符和j字符相等则+0，如果不相等则+1为 i和j的编辑距离。
应该用动态规划：
int dp[m+1][n+1] //定义长度为i的字串和长度为j的字串之间的编辑距离
两个字符串最前面插入一个空字符，初始化[i][0] base case 为i，初始化[0][j] base case 为j；
编写状态转移方程。
*/
int cal_distance(string sline1,string sline2)
{
if ((sline1.empty())&&(sline2.empty())){
return 0;
}
if ((sline1.empty())&&(!sline2.empty())){
return sline2.size();
}
if ((!sline1.empty())&&(sline2.empty())){
return sline1.size();
}
sline1.insert(sline1.begin(),' ');
sline2.insert(sline2.begin(),' ');
int m = sline1.size();
int n = sline2.size();
vector<vector<int>> dp(m, vector<int>(n,0));//定义长度为i的字串和长度为j的字串之间的编辑距离
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++){
int add;
if (sline1[i] == sline2[j]){
add = 0;
}
else{
add = 1;
}
int dp1 = dp[i-1][j-1] + add;
int dp2 = dp[i-1][j]+1;
int dp3 = dp[i][j-1]+1;
if (dp1>dp2){
dp1 = dp2;
}
if (dp1>dp3){
dp1 = dp3;
}
dp[i][j] = dp1;
}
}
return dp[m-1][n-1];
}
int _tmain(int argc, _TCHAR* argv[])
{
string sline1, sline2;
while(cin >> sline1)
{
cin >> sline2;
int length = cal_distance(sline1,sline2);
cout << length <<endl;
}
return 0;
}
发表于 2021-04-18 16:27:17
回复(0)
动态规划，dp[i][j]代表i到j的编辑距离
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String a = in.nextLine();
String b = in.nextLine();
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][n + 1];
//初始化状态
for(int i = 1;i <= m;i++){
dp[i][0] = i;
}
for(int j = 1;j <= n;j++){
dp[0][j] = j;
}
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(a.charAt(i - 1) == b.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = Math.min(dp[i - 1][j - 1],Math.min(dp[i - 1][j],dp[i][j - 1])) + 1;
}
}
}
System.out.println(dp[m][n]);
}
}
发表于 2021-04-15 15:37:45
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
String s1 = " " + cin.next(), s2 = " " + cin.next();
System.out.println(calStringDistance(s1, s2));
}
}
public static int calStringDistance(String charA, String charB) {
int n = charA.length(), m = charB.length();
int[][] lev = new int[n][m];
int cost;
for (int i = 0; i < n; i++) lev[i][0] = i;
for (int j = 0; j < m; j++) lev[0][j] = j;
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
char ch1 = charA.charAt(i), ch2 = charB.charAt(j);
if (ch1 == ch2) cost = 0;
else cost = 1;
lev[i][j] = getMin(lev[i - 1][j] + 1, lev[i][j - 1] + 1, lev[i - 1][j - 1] + cost);
}
}
return lev[n - 1][m - 1];
}
public static int getMin(int a, int b, int c) {
a = Math.min(a, b);
b = Math.min(b, c);
return Math.min(a, b);
}
}
发表于 2020-08-22 20:30:14
回复(0)
最小编辑距离，经典的动态规划问题之一，类似的还有最大公共子串，最大公共序列，最大递增序列，01
背包问题等等
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
string s1,s2;
while(cin>>s1>>s2){
int len1=s1.size();
int len2=s2.size();
vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));
for(int i=1;i<=len1;i++){
dp[i][0]=i;
}
for(int j=1;j<=len2;j++){
dp[0][j]=j;
}
dp[0][0]=0;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1];
else{
int tem=min(dp[i-1][j],dp[i][j-1]);
dp[i][j]=min(dp[i-1][j-1],tem)+1;
}
}
}
cout<<dp[len1][len2]<<endl;
}
return 0;
}
发表于 2020-02-16 20:08:55
回复(0)
动态规划算法之一,编辑距离。不要搞得这么复杂吓死人，看帖了解距离矩阵，按公式编程即可。
贴出参考的帖子地址：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String strA = in.next();
String strB = in.next();
int cost = strEditCost(strA, strB);
System.out.println(cost);
}
in.close();
}
public static int strEditCost(String strA, String strB){
int m = strA.length() + 1;
int n = strB.length() + 1;
int[][] dp = new int[m][n];
// 初始化0列0行先,这个距离是可以预先知道的
for(int i = 0;i<m;i++) {
dp[i][0] = i;
}
for(int j = 0;j<n;j++) {
dp[0][j] = j;
}
// 当 i,j都是大于0时
for(int i = 1;i<m;i++) {
for(int j=1;j<n;j++) {
int cout1 = Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1);
int dc = 1;
if(strA.charAt(i-1) == strB.charAt(j-1)) {
dc = 0;
}
int cout2 = Math.min(cout1,dp[i-1][j-1]+dc);
dp[i][j] = cout2;
}
}
return dp[m-1][n-1];
}
}
发表于 2019-11-02 23:47:13
回复(1)
#include<iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
string a,b;
while(cin>>a>>b)
{
int n = a.size(),m = b.size();
vector<vector<int>>dp(n+1,vector<int>(m+1));/*dp[x][y]代表将a字符串的前x个字符（从1编号，a的前1个字符为a[0],
前两个字符为a[0]和a[1]）转换成b字符串的前y个字符*/
for (int i=0; i<=n; i++) dp[i][0] = i;
for (int j=0; j<=m; j++) dp[0][j] = j;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; ++j)
{
int d1 = dp[i-1][j] +1,d2 = dp[i][j-1]+1,d3 = dp[i-1][j-1];
if(a[i-1]!=b[j-1]) d3+=1; //注意由于a的前i-1个字符时从1编号，则第i个字符也是从1编号，为a[i-1]，同理b[j-1]
dp[i][j] = min(min(d1,d2),d3);
}
cout<<dp[n][m]<<endl;
}
return 0;
}
发表于 2018-07-08 01:01:58
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
String s1=input.nextLine();
String s2=input.nextLine();
System.out.println(stringDistance(s1.toCharArray(), s2.toCharArray()));
}
}
public static int stringDistance(char[] a, char[] b){
int[][] len = new int[a.length + 1][b.length + 1];
for (int i = 0; i < len.length; i++) {
len[i][0] = i;
}
for (int j = 0; j < len[0].length; j++) {
len[0][j] = j;
}
for (int i = 1; i < len.length; i++) {
for (int j = 1; j < len[0].length; j++) {
if (a[i - 1] == b[j - 1]) {
len[i][j] = len[i - 1][j - 1];
} else {
len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1;
}
}
}
return len[len.length - 1][len[0].length - 1];
}
}
发表于 2018-06-29 15:56:37
回复(0)
import java.util.Scanner;
public class P052StringDistance {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String strA = sc.next();
String strB = sc.next();
System.out.println(calStrDis(strA, strB, strA.length(), strB.length()));
}
sc.close();
}
public static int calStrDis(String strA, String strB, int m, int n) {
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if(i == 0)//strA为空。
dp[i][j] = j;
else if(j == 0)//strB为空。
dp[i][j] = i;
else if(strA.charAt(i - 1) == strB.charAt(j - 1))//strA和strB最后一个字符相同。
dp[i][j] = dp[i-1][j-1];
else//strA和strB最后一个字符不同。
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]);//strA的所有操作：插入，删除，替换。 }
}
return dp[m][n];
/*//直接递归，运行超时。
if(m == 0) return n;
if(n == 0) return m;
if(strA.charAt(m - 1) == strB.charAt(n - 1))
return calStrDis(strA, strB, m - 1, n - 1);
return 1 + min(calStrDis(strA, strB, m, n - 1), calStrDis(strA, strB, m - 1, n), calStrDis(strA, strB, m - 1, n - 1));
*/
}
public static int min(int x, int y, int z) {
if(x < y && x < z)
return x;
else if(y < x && y < z){
return y;
else
return z;
}
发表于 2018-06-12 22:55:51
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()){
String s1=in.nextLine();
String s2=in.nextLine();
System.out.println(calStringDistance(s1,s2));
}
}
private static int calStringDistance(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
if(len1==0){
return len2;
}
if(len2 ==0){
return len1;
}
int[][] a = new int[len1+1][len2+1];
for(int i=0;i<len1+1;i++){
a[i][0]=i;
}
for(int j=0;j<len2+1;j++){
a[0][j] =j;
}
for(int i=1;i<len1+1;i++){
for(int j=1;j<len2+1;j++){
int temp=Math.min(a[i-1][j]+1, a[i][j-1]+1);
int num=c1[i-1]==c2[j-1]?0:1;
a[i][j]=Math.min(temp, a[i-1][j-1]+num);
}
}
return a[len1][len2];
}
}
编辑于 2017-04-17 16:50:34
回复(0)
import java.util.*;
/**
*
* @author zhangxf0406
* 动态规划--计算字符串的距离
*/
public class Main {
public static void calStringDistance(char[] source , char[]
target){
int [][]dp = new int[source.length + 1][target.length + 1];
for(int i = 0 ; i < source.length + 1 ; i++)
dp[i][0] = i;
for(int j = 0 ; j < target.length + 1 ; j++)
dp[0][j] = j;
for(int i = 1 ; i < source.length + 1 ; i++){
for(int j = 1 ; j < target.length + 1 ; j++){
if(source[i-1] == target[j-1])
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1 ,
dp[i][j-1] + 1) , dp[i-1][j-1] + 1);
}
}
}
System.out.println(dp[source.length][target.length]);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
String a = scanner.next();
String b = scanner.next();
char [] source = a.toCharArray();
char [] target = b.toCharArray();
calStringDistance(source, target);
}
scanner.close();
}
}
编辑于 2017-03-09 10:59:59
回复(1)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
String str1 = scan.nextLine();
String str2 = scan.nextLine();
System.out.println(calStringDistance(str1, str2));
}
scan.close();
}
private static int calStringDistance(String str1, String str2){
int len1 = str1.length();
int len2 = str2.length();
int[][] distance = new int[len1+1][len2+1];
for(int i=1; i<=len1; i++){
distance[i][0]=i;
}
for(int j=1; j<=len2; j++){
distance[0][j]=j;
}
int a=0, b=0, c=0;
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
a = distance[i][j-1]+1;
b = distance[i-1][j]+1;
c = str1.charAt(i-1)==str2.charAt(j-1)? distance[i-1][j-1]:distance[i-1][j-1]+1;
distance[i][j]= Math.min(Math.min(a,b), c);
}
}
return distance[len1][len2];
}
}
发表于 2016-08-24 19:31:10
回复(2)
import java.util.Scanner;
public class Main{
public static int min(int a,int b,int c){//输出三个数的最小值
int min=a>b?b:a;
return min<c?min:c;
}
public static int dp(String a,String b){
int m=a.length();
int n=b.length();
int[][] arr=new int[m+1][n+1];
for (int i = 1; i <=m; i++) {
arr[i][0]=i;
for (int j = 1; j <=n; j++) {
arr[0][j]=j;
if (a.charAt(i-1)==b.charAt(j-1)) {
arr[i][j]=arr[i-1][j-1];
}
else {
arr[i][j]=min(arr[i-1][j], arr[i-1][j-1], arr[i][j-1])+1;
}
}
}
return arr[m][n];
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
String a=scanner.next();
String b=scanner.next();
System.out.println(dp(a, b));
}
}
}
发表于 2016-08-17 12:02:32
回复(0)
//思路主要：
u
如果两个串的第一个字符相同
，如A=xabcdae和B=xfdfa，只要计算
A[2,…,7]=abcdae和B[2,…,5]=fdfa的距离就可以了。
u
如果两个串的第一个字符不相同
，那么可以进行如下的操作：
1．删除A串的第一个字符，然后计算A[2,…,lenA]和B[1,…,lenB]的距离。
2．删除B串的第一个字符，然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
3．修改A串的第一个字符为B串的第一个字符，然后计算A[2,…,lenA]和
B[2,…,lenB]的距离。
4．修改B串的第一个字符为A串的第一个字符，然后计算A[2,…,lenA]和
B[2,…,lenB]的距离。
5．增加B串的第一个字符到A串的第一个字符之前，然后计算
A[1,…,lenA]和B[2,…,lenB]的距离。
6．增加A串的第一个字符到B串的第一个字符之前，然后计算
A[2,…,lenA]和B[1,…,lenB]的距离。
动态规划思路为：
动态规划思路为：
* 设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 … ai）
* 设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 … bj）
*
* 设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
* 当ai==bj时 显然 L(i,j) = L(i-1,j-1)
* 当ai!=bj时
*
* 若将它们修改为相等，则对两个字符串至少还要操作L(i-1,j-1)次
* 若删除ai或在bj后添加ai，则对两个字符串至少还要操作L(i-1,j)次
* 若删除bj或在ai后添加bj，则对两个字符串至少还要操作L(i,j-1)次
* 此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1
*
* 显然，L(i,0)=i，L(0,j)=j, 再利用上述的递推公式，可以直接计算出L(i,j)值。
package com.wenjie.huawei;
import java.util.Scanner;
public class CalStringDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str1 = sc.nextLine();
String str2 = sc.nextLine();
System.out.println(stringDistance(str1.toCharArray(),str2.toCharArray()));
}
}
private static int stringDistance(char[] a, char[] b) {
int[][] len = new int[a.length + 1][b.length + 1];
for (int i = 0; i < len.length; i++) {
len[i][0] = i;
}
for (int j = 0; j < len[0].length; j++) {
len[0][j] = j;
}
for (int i = 1; i < len.length; i++) {
for (int j = 1; j < len[0].length; j++) {
if (a[i - 1] == b[j - 1]) {
len[i][j] = len[i - 1][j - 1];
} else {
len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1;
}
}
}
return len[len.length - 1][len[0].length - 1];
}
}
编辑于 2017-06-14 21:27:16
回复(6)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String strA = in.next();
String strB = in.next();
int ic = 1;
int dc = 1;
int rc = 1;
int cost = strEditCost(strA, strB, ic, dc, rc);
System.out.println(cost);
}
in.close();
}
public static int strEditCost(String strA, String strB, int ic, int dc, int rc){
/* 字符串之间的距离，编辑距离，将strA编辑成strB所需的最小代价
* 编辑操作包括插入一个字符、删除一个字符、替换一个字符
* 分别对应的代价是ic、dc、rc，insert cost、delete cost、replace cost
* strA[x-1]代表strA的第x个字符，注意下标是从0开始的,strA[y-1]代表strA的第y个字符
* 定义一个代价矩阵为(N+1)*(M+1)，M N 表示strA strB的长度
* dp[x][y]表示strA的前x个字符串编辑成 strB的前y个字符所花费的代价
* dp[x][y]是下面几种值的最小值：
* 1、dp[x][y] = dp[x-1][y] + dc
* dp[x-1][y]将strA的前x-1个字符编辑成strB的前y个字符的代价已知，
* 那么将将strA的前x个字符编辑成strB的前y个字符的代价dp[x][y]就是dp[x-1][y] + dc
* 相当于strA的前x-1个字符编辑成strB的前y个字符，现在变成了strA的前x个字符，增加了一个字符，要加上删除代价
* 2、dp[x][y] = dp[x][y-1] + ic
* dp[x][y-1]将strA的前x个字符编辑成strB的前y-1个字符的代价已知，
* 现在变为strB的前y个字符，相应的在strA前x个操作代价的基础上插入一个字符
* 3、dp[x][y] = dp[x-1][y-1]
* dp[x-1][y-1]将strA的前x-1个字符编辑成strB的前y-1个字符的代价已知，
* strA的第x个字符和strB的第y个字符相同，strA[x-1] == strB[y-1]，没有引入操作
* 4、dp[x][y] = dp[x-1][y-1] + rc
* strA的第x个字符和strB的第y个字符不相同，strA[x-1] ！= strB[y-1]，
* 在strA的前x-1个字符编辑成strB的前y-1个字符的代价已知的情况下，
* 计算在strA的前x字符编辑成strB的前y个字符的代价需要加上替换一个字符的代价
* */
int m = strA.length();
int n = strB.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= n; i++) dp[0][i] = i*ic;
for (int i = 1; i <= m; i++) dp[i][0] = i*dc;
for (int x = 1; x <= m; x++) {
for (int y = 1; y <= n; y++) {
int cost1 = dp[x-1][y] + dc;
int cost2 = dp[x][y-1] + ic;
int cost3 = 0;
if(strA.charAt(x-1) == strB.charAt(y-1))
cost3 = dp[x-1][y-1];
else
cost3 = dp[x-1][y-1] + rc;
dp[x][y] = Math.min(cost1, cost2);
dp[x][y] = Math.min(dp[x][y], cost3);
}
}
return dp[m][n];
}
}
编辑于 2017-06-28 12:54:18
回复(5)
python solution:
def editDistance(str1, str2):
len1, len2 = len(str1) + 1, len(str2) + 1
dp = [[0 for i in range(len2)] for j in range(len1)]
for i in range(len1):
dp[i][0] = i
for j in range(len2):
dp[0][j] = j
for i in range(1, len1):
for j in range(1, len2):
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]))
return dp[-1][-1]
while True:
try:
print(editDistance(input(), input()))
except:
break
发表于 2017-10-17 14:57:35
回复(11)
def edit_distance(s1,s2): len1 = len(s1) + 1 len2 = len(s2) + 1 edit = [[i + j for j in range(len2)] for i in range(len1)] for i in range(1,len1): for j in range(1,len2): if s1[i-1] == s2[j-1]: d = 0 else: d = 1 edit[i][j] = min(edit[i][j-1]+1,edit[i-1][j]+1,edit[i-1][j-1]+d) return edit[-1][-1] while True: try: print(edit_distance(input(), input())) except:break
推荐大家看个文章，什么都懂了
发表于 2020-05-14 15:39:57
回复(5)
//典型的动态规划优化编辑器问题
//参考博客 http://blog.csdn.net/shizheng163/article/details/50988023
#include<iostream>
#include <string>
#include <vector>
using namespace std;
int calStringDistance(string a,string b){
int n = (int)a.size(),m = (int)b.size();
vector<vector<int>>dp(n+1,vector<int>(m+1,0));
dp[0][0] = 0;//dp[x][y]代表将a字符串前x个字符修改成b字符串前y个字符
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) {
int one = dp[i-1][j] +1,two = dp[i][j-1]+1,three = dp[i-1][j-1];
if(a[i-1]!=b[j-1]) three+=1;
dp[i][j] = min(min(one,two),three);
}
}
return dp[n][m];
}
int main(){
string a,b;
while(cin>>a>>b)
cout<<calStringDistance(a, b)<<endl;
return 0;
}
编辑于 2016-04-01 21:30:35
回复(7)
问题信息
难度：
233条回答
4421收藏
44231浏览
通过挑战的用户
查看代码-
2023-01-18 20:04:38
-
2023-01-10 14:43:09
-
2023-01-07 16:18:34 -
2022-12-21 11:40:54
-
2022-11-25 20:31:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
