[数据结构与算法] 【字符串动态规划dp】Changing a String

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【字符串动态规划dp】Changing a String -> 正文阅读

[数据结构与算法]【字符串动态规划dp】Changing a String

博客主页: https://blog.csdn.net/qq_50285142
欢迎点赞👍收藏?关注?留言 📝 如有错误，敬请指正
🎈虽然生活很难，但我们也要一直走下去🎈

原题链接

题意：
给定两个字符串，可以进行删除，替换，添加的操作，求把字符串A变为字符串B的最小操作次数，并且写出操作的具体情况

思路：
动态规划：
状态表示：
$f [i] [j]$ 表示字符串a前i个字符变为字符串b前j个字符，所需要的最小操作次数
状态转移：
$a [i] = b [j]$ 时， $f [i] [j] = f [i ? 1] [j ? 1]$ 第i位和第j位肯定不需要改变，所以就相等了
否则 $f[i][j] = 1 + min({f[i-1][j],f[i][j-1],f[i-1][j-1]})$
可能a的第i位和b的第j位不相等就对应 $f [i ? 1] [j ? 1] + 1$

操作的话，我们可以根据字符串末尾的操作次数和前字符串长度减少一的相比，判断是哪个操作，判断之后操作完那么对应的长度要进行改变，因为我们是倒推的，要对长度有减的操作，这样才能一直往字符串前进行操作。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const int N = 1005,M = 2e5+5;

int n,m,k;
int f[N][N]; 
char a[N],b[N];

void solve()
{
	cin>>a+1>>b+1;
	n = strlen(a+1),m = strlen(b+1);
	for(int i=0;i<=n;i++) f[i][0] = i;
	for(int i=0;i<=m;i++) f[0][i] = i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i]==b[j])
				f[i][j] = f[i-1][j-1];
			else
				f[i][j] = 1 + min({f[i-1][j],f[i][j-1],f[i-1][j-1]});
		}
	
	cout<<f[n][m]<<'\n';
	while(n>0 or m>0)
	{
		if(n and f[n][m]==f[n-1][m]+1)
		{
			cout<<"DELETE "<<n<<'\n';
			n--;
		}
		else if(m and f[n][m]==f[n][m-1]+1)
		{
			cout<<"INSERT "<<n+1<<" "<<b[m]<<'\n';
			m--;
		}
		else if(n and m and f[n][m]==f[n-1][m-1])
		{
			n--;
			m--;
		}
		else
		{
			cout<<"REPLACE "<<n<<" "<<b[m]<<'\n';
			n--,m--;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _;
//	cin>>_;
	_ = 1;
	while(_--)
	{
		solve();
	}
	return 0;
}