C - Word Ladder题解

2024-09-09 04:52

文章标签 题解 word ladder

本文主要是介绍C - Word Ladder题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C - Word Ladder 题解

解题思路：

先输入两个字符串S 和t

然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次）

开始替换时：

tips: 字符串下标以0开始

我们定义两个变量a和b，用于记录当前遍历到的字符

首先是判断：如果这时a已经==b了，那么就跳过，不用管；

如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。

这样输出可以免了还要搞个string类数组去存一大堆东西，搞不好还容易错

然后再倒过来看：

还是熟悉的a=s[i],b=t[i]，还是熟悉的判断，但是这一次我们是查漏补缺（也就是看看哪个地方还没改为t的样子）

为什么第一次不直接全部替换掉而第二次又来从后往前找呢？

因为第一次找我们要保证『字符串数组的词典顺序』，而第二次从后往前就是找那个还没换成T而已.

上代码：

#include <iostream>		// 基本输入输出流
#include <algorithm>	// 通用算法（排序、查找、去重、二分查找等）
#include <vector>		// 动态数组（空间不够会自动扩容）
#include <queue>		// 队列（先进先出）
#include <stack>		// 栈（先进后出）
#include <set>			// 集合（有序不重复）
#include <map>			// 键值对容器（映射）
#include <list>			// 双向链表
#include <math.h>		// 数学函数
#include <functional>	// 通用的函数绑定和调用机制#define endl '\n'
#define pii pair<int, int>
#define pdd pair<double, double>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long
using namespace std;const int inf = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10, M = N << 1;
char a, b;
int m;
void solve() {string s, t;cin >> s >> t;int n = s.size();for(int i = 0; i < n; i++){if(s[i] != t[i]) m++;}cout << m << endl;for(int i = 0; i < n; i++){a = s[i], b = t[i];if(a == b)continue;if(a > b){s[i] = b;cout << s << endl;}}for(int i = n - 1; i >= 0; i--){a = s[i], b = t[i];if(a == b) continue;s[i] = b;cout << s << endl;}
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;while(t--) solve();return 0;
}