字符串最小变换次数

#include <iostream>
using namespace std;
int main(){

    string str1, str2;
    cin >> str1 >> str2;
    int row = str1.size() + 1, col = str2.size() + 1;
    int dp[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[i - 1] == str2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }else{
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            dp[i][j] = min(dp[i][j], dp[i - 1][j]  + 1);
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
        }
    }
    cout << dp[row - 1][col - 1] << endl;
    return 0;
}

设dp[i][j] 表示字符串s1[:i]和s2[:j]达到题目要求的最小变换次数。如果字符s1[i]和s2[j]相等的话，那么dp[i][j]的值就是dp[i-1][j-1]，这一步不用变换，如果不相等的话，变换一个字符加一次操作，就是dp[i-1][j-1]+1。当然dp[i][j]还有可能是s1[:i-1]与s2[:j]或者s1[:i]与s2[:j-1]变换过来可能总的变换次数更少。所以就选其中最小的即可。实际编程应注意动态规划时有初始化，需要注意矩阵的索引和字符串索引别弄错了。

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    const int rows = s1.size() + 1, cols = s2.size() + 1;
    vector<vector<int> > dp(rows, vector<int>(cols, 0));
    for (int i = 0; i < rows; i++) dp[i][0] = i;
    for (int j = 0; j < cols; j++) dp[0][j] = j;
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = dp[i-1][j-1] + 1;
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
        }
    }
    cout << dp[rows-1][cols-1] << endl;
    return 0;
}

importjava.util.Scanner;

	/*思路：



	开一个二维数组d[i][j]来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、



	插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求。



	具体算法：



	首先给定第一行和第一列，然后，每个值d[i,j]这样计算：d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+(s1[i] == s2[j]?0:1));



	最后一行，最后一列的那个值就是最小编辑距离



	*/



	publicclassMain {



	    publicstaticvoidmain(String[] args) {



	        Scanner sc=newScanner(System.in);



	        String str1=sc.nextLine().toLowerCase();



	        String str2=sc.nextLine().toLowerCase();



	        intres=minChangeSteps(str1,str2);



	        System.out.println(res);



	    }



	    publicstaticintminChangeSteps(String s1,String s2){



	        int[][] dp=newint[s1.length()][s2.length()];



	        for(inti =0; i <s1.length() ; i++) {



	            dp[i][0]=i;



	        }



	        for(inti =0; i <s2.length() ; i++) {



	            dp[0][i]=i;



	        }



	        for(inti =1; i <s1.length() ; i++) {



	            for(intj =1; j <s2.length() ; j++) {



	                dp[i][j]=Math.min(dp[i-1][j]+1,



	                        Math.min(dp[i][j-1]+1,dp[i-1][j-1]+(s1.charAt(i) == s2.charAt(j)?0:1)));



	            }



	        }



	        returndp[s1.length()-1][s2.length()-1];



	    }



	}

#include<iostream>
#include<string>
using namespace std;

const int maxn = 1005;
int dp[maxn][maxn];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int m = s1.length(), n = s2.length();
    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[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int dp[1010][1010];
string s1, s2;

int Min(int x, int y, int z) {
	return min(x, min(y, z));
}

int DP(int l, int r) {
	if (dp[l][r] != -1) {
		return dp[l][r];
	}
	if (s1[l - 1] == s2[r - 1]) {
		dp[l][r] = DP(l - 1, r - 1);
		return dp[l][r];
	} else {
		dp[l][r] = Min(DP(l - 1, r - 1), DP(l - 1, r), DP(l, r - 1)) + 1;
		return dp[l][r];
	}
}

int main() {
	cin >> s1 >> s2;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < (int)s1.size(); i++) {
		dp[i + 1][0] = (i + 1);
	}
	for (int i = 0; i < (int)s2.size(); i++) {
		dp[0][i + 1] = (i + 1);
	}
	dp[0][0] = 0;
	cout << DP((int)s1.size(), (int)s2.size()) << "\n";
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s1, s2;
    cin>>s1>>s2;
    int n = s1.length(), m = s2.length();
    int a[n+1][m+1];
    for(int i=0;i<=n;i++)
        a[i][0] = i;
    for(int i=0;i<=m;i++)
        a[0][i] = i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(s1[i]==s2[j])
                a[i][j] = a[i-1][j-1];
            else
                a[i][j] = a[i-1][j-1] + 1;
            a[i][j] = min(a[i][j], a[i-1][j]+1);
            a[i][j] = min(a[i][j], a[i][j-1]+1);
        }
    cout<<a[n-1][m-1]<<endl;

    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc =  new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        int[][] dis = new int[str1.length()+1][str2.length()+1];
        for(int i=0; i<=str1.length();i++){
            dis[i][0]=i;
        }
        for(int i=0; i<=str2.length();i++){
            dis[0][i]=i;
        }
        for(int i=1; i<=str1.length();i++){
            for(int j=1;j<=str2.length(); j++){
                dis[i][j]=Math.min(Math.min(dis[i-1][j]+1,dis[i][j-1]+1),dis[i-1][j-1]+(str1.charAt(i-1)==str2.charAt(j-1)?0:1));
            }
        }
        System.out.println(dis[str1.length()][str2.length()]);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        // 编辑距离
        Scanner scan  = new Scanner(System.in);
        String s1 = scan.nextLine();
        String s2 = scan.nextLine();
        int m = s1.length();
        int 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-1]+1, Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
                    
            }
        System.out.println(dp[m][n]);
    }
}

// 假定变换规则是 1. 串1长度大于串2的时候，删除字符
// 2. 串1长度小于串2的时候，添加字符
// 3. 串1长度等于串2的时候，替换字符
// 如果仅仅是这种思路，那么只能通过50%。。。
var change=readline().split('');
var old=readline().split('');
function dp(old,mynow){
    // 四种情况
    let old_len=old.length;
    let now_len=mynow.length;
    // 跳过，看下一个数
    // 插入，删除，更改
    let ins_spl=mynow.slice(0,now_len-1);
    let del_spl=old.slice(0,old_len-1)
    let ins_old=old.slice(0,old_len)
    let del_now=mynow.slice(0,now_len)
    // 结束条件: 1. 如果数字一致，那么后面两个数不用改变
    if(now_len==1&&old_len==1&&old[0]==mynow[0]){
        return 0
    }else if(now_len==1||old_len==1){
        // 2. 否则改变一次才可以
        return 1
    }
    if(mynow[now_len-1]==old[old_len-1]){
        return dp(del_spl,ins_spl)
    }else{
        return 1+Math.min(dp(ins_old,ins_spl),dp(del_spl,del_now),dp(del_spl,ins_spl))
    } 
}
console.log(dp(old,change))

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
    string a,b;
    cin>>a>>b;
    int an=a.size();
    int bn=b.size();
    int dp[1001][1001]={0};
    for(int i = 0; i <= an; ++i){
        dp[i][0] = i;
    }
    for(int i = 0; i <= bn; ++i){
        dp[0][i] = i;
    }
    for(int i=1;i<=an;i++)
    {
        for(int j=1;j<=bn;j++)
        {
            if(a[i]==b[j])
                dp[i][j]=dp[i-1][j-1];
            else
            {
                int temp=min(dp[i-1][j]+1,dp[i][j-1]+1);
                dp[i][j]=min(dp[i-1][j-1]+1,temp);
            }
        }
    }
    cout<<dp[an][bn];
    return 0;
}

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    string s1,s2;
    cin>>s1>>s2;
    int count = 0;
    int row = s1.length();
    int col = s2.length();
    int dp[row][col] ;//表示s10-s1i到s20-s2j的修改距离,包括添加，删除，或者更改
    for(int i = 0;i<row;i++)
        dp[i][0] = i;
    for(int j = 0;j<col;j++)
        dp[0][j] = j;
    for(int i = 1;i<row;i++){
        for(int j = 1;j<col;j++){
            dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);
            dp[i][j] = min(dp[i][j],dp[i-1][j-1]+(s1[i]==s2[j]?0:1));
        }
    }
    cout<<dp[row-1][col-1]<<endl;
    
}

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define Down(i,a,b) for(int i = a; i >= b; i--)
#define ms(a,x) memset(a,x,sizeof(a))
const int maxn = 1001;

int dp[maxn][maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(dp,0);    //初始化
    string s1,s2;
    cin >> s1 >> s2;
    int len1 = s1.length();
    int len2 = s2.length();
    Up(i,0,len1)
    {
        dp[i][0] = i;
    }
    Up(i,0,len2)
    {
        dp[0][i] = i;
    }
    Up(i,1,len1)
    {
        Up(j,1,len2)
        {
            dp[i][j] = s1[i-1]==s2[j-1] ? dp[i-1][j-1] : min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
        }
    }
    cout << dp[len1][len2] << endl;
    return 0;
}