题目链接：C - Word Ladder
题目：
样例：
分析：
不要被题目所吓到，一切长题目都是纸老虎。题目大意就是给你两个字符串s和t，一次只能更换一个字母，求s变到t更换的次数，并输出每次更换一个字母后的最小字典序字符串。题意好理解，可以直接暴力，大力出奇迹。但是有没有更好的方法呢？既然问了就说明是有的。最主要的是要搞清每次更换的是哪个字母。我们可以先考虑特殊情况，假设s中的每个字母都是大于等于t中对应的那个字母，如：s=bbb，t=aaa。第一次s=bbb更换有三种情况：abb bab bba 最小的那个是abb。第二次s=abb更换有两种：aab aba 最小的那个是aab。第三次s=aab可直接更换为t=aaa。可看出当s>=t时更换的次序是从左到右依次更换的。同理可知当s中的每个字母都是小于等于t中对应的那个字母时更换的次序是从右到左依次更换的。由特殊到一般，s中字母既有大于还有小于t中对应的字母时，如样例中：s=afwgebrw，t=oarbrenq。s中字母大于t中相应位置的下标为：12367，小于的为：045。而s到t更换的次序为：12367 540，首先是大于的从左往右，然后是小于的从右往左。知道这就好做了。我们可以用一个动态数组记录每次要改变字母的位置，然后改变就好了。当然也可以用双向队列deque来做，从后往前扫描，s中哪个字母>t中对应的字母是时插入队列的头部，小于时插入队列的尾部，这一套下来后可也得出大于的是从左往右的，小于的是从右往左的。话不多说直接上 code
GAME OVER!!!
END!
方法一：直接暴力
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
vector<string>ans;
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string s, t;
int k; //s和t中不同的字母个数
cin >> s >> t;
int n = s.size();
while(s != t) {
k ++;
string idx(n, 'z');
for(int i = 0; i < n; i++ ) {
if(s[i] != t[i]) {
string tmp = s;
tmp[i] = t[i];
idx = min(idx,tmp); //得到字典序最小的那个字符串
}
}
ans.push_back(idx); //把每次最小的字符串加入到答案数组中
s = idx; //把这次修改后的字符串赋值给s
}
cout << k << endl;
for(auto i : ans)
cout << i << endl;
return 0;
}
方法二：记录位置
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string s, t;
cin >> s >> t;
vector<string> ans;
vector<int> x; //存要改变字母的下标
int n = s.size();
for(int i = 0; i < n; i++ ) {//大于 从左往右
if(s[i] > t[i]) x.push_back(i);
}
for(int i = n - 1; i >= 0; i-- ) {//小于 从右往左
if(s[i] < t[i]) x.push_back(i);
}
int k = x.size();
for(int i = 0;i < k; i++ ) {
s[x[i]] = t[x[i]];
ans.push_back(s);
}
cout << k << endl;
for(auto i : ans) cout << i << endl;
return 0;
}
方法三：deque
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string s, t;
cin >> s >> t;
deque<int> x;
for(int i = s.size() - 1; i >= 0; i --) {//队列从后往前扫描
if(s[i] > t[i]) x.push_front(i); //大于的插入头部
if(s[i] < t[i]) x.push_back(i); //小于的插入尾部
}
int k = x.size();
cout << k << endl;
for(auto i : x) {
s[i] = t[i];
cout << s << endl;
}
return 0;
}