【蓝桥杯选拔赛真题41】C++操作字符串第十四届蓝桥杯青少年创意编程大赛算法思维 C++编程选拔赛真题解析

C++操作字符

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

C++操作字符

第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题

一、题目要求

1、编程实现

给定两个字符串S1和S2(1<S1长度<100,1<S2长度<100),然后按照以下三种操作,将S1转为S2,问最少操作几次可以完成.可对字符串进行三种操作:
1)插入一个字符;
2)删除一个字符;
3)修改一个字符。

例如:
S1=abcd，S2=ebde，S1转为S2最少需要操作3次

第一次操作：将abcd中的字符a修改成e，修改后为ebcd

第二次操作：将ebcd中的字符c删除，删除后为ebd

第三次操作：在ebd末端插入字符e，插入后为ebde

经过3次操作，字符串abcd转为字符串ebde

2、输入输出

输入描述：第一行输入一个字符串S1(1<S1长度<100)

第二行输入一个字符串S2(1<S2长度<100)

输出描述：只有一行，一个整数，即将S1转为S2的最少操作次数

输入样例：

abcd
ebde

输出样例：

二、算法分析

从给定题目的初步分析可以看出，这是一道关于字符串题目，题目的核心思路是要求将一个字符串经过编辑后变成另外一个字符串的最少次数，也就是编辑距离题目
这也是比较经典的一道算法题目，可以利用动态规划的思路进行求解
可以利用一个二维数组dp来存放中间计算结果的最小编辑距离。dp[i][j]表示将str1的前i个字符转换成str2的前j个字符所需的最少操作次数
如此将两个字符串都遍历结束即可得到我们要的答案

三、程序编写

#include <iostream>
#include <string>
using namespace std;
int dp[105][105]; 
int dist_dp(string str1, string str2) 
{
    int m = str1.length();
    int n = str2.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++) 
		{
			dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1;
		   	if (str1[i-1]==str2[j-1])
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            else
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    return dp[m][n];
} 
int main() 
{
    string str1, str2;
    cin >> str1 >> str2;
    cout << dist_dp(str1, str2) << endl;
    return 0;
}

四、程序说明

首先需要导入输入输出流头文件
接着再次导入输入输出流格式控制头文件
然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
声明一个全局二维数组dp，用于存储计算过程中的中间结果。数组的大小为105×105，这是为了保证能够容纳输入字符串的最大长度。
dist_dp函数接受两个字符串str1和str2作为输入，并返回它们之间的编辑距离
在函数中，首先初始化dp数组的边界条件：将dp[i][0]设置为i，表示将字符串str1的前i个字符删除，即编辑距离为i
将dp[0][j]设置为j，表示将字符串str2的前j个字符删除，即编辑距离为j
接下来，使用两个嵌套循环遍历dp数组的剩余部分
对于每个位置(i,j)，根据当前位置的字符相等与否，选择下面四种操作中的最小值，更新dp[i][j]的值
删除字符：在dp[i][j-1]的基础上再删除一个字符，编辑距离加一
插入字符：在dp[i-1][j]的基础上再插入一个字符，编辑距离加一
替换字符：在dp[i-1][j-1]的基础上进行字符替换，编辑距离加一（如果替换的字符相同，则不需要额外的编辑操作）
循环结束后，dp[m][n]即为字符串str1和str2的编辑距离
在main函数中，首先读入两个字符串str1和str2，然后调用dist_dp函数计算它们之间的编辑距离，并将结果输出
最后返回0，程序结束

本文作者：小兔子编程作者首页：https://blog.csdn.net/frank2102