[ABC370C] Word Ladder 题解

题目描述：

给予两个相等长度的序列，\(S\) 与 \(T\) ，以及一个空数组 \(X\) ，每在 \(S\) 上修改一个字符，便将修改后的 \(S\) 加入 \(X\) 中，直到 \(S\) 与 \(T\) 相同。(输出字典序最小的 \(X\) 数组)

拿过题一看，感觉还是蛮简单的，本题主要的难点在字符串的字典序上。

字符串字典序的定义：

1. 若两个字符串的长度相等，从左向右依字符逐个比较，第一对不相等的字符的大小即为这两对字符串的大小。
2. 若长度不相等，则较长的字符串较大。
3. 若长度相等且每个字符都相等，则这两个字符串相等。

则此题的解法其实就是一种贪心：

\(S\) 中与 \(T\) 不同的字符分为两种，一种为大于 \(T\) 中同位置字符的，另一种相反。在修改第一种情况时，\(S\) 的字典序变小，修改第二种时， \(S\) 字典序变大。所以要先修改第一种。

所以先从左向右扫，若 s[i]!=t[i]&&s[i]>t[i] 就修改 \(S\) 字符串，可证得这样修改的字符串字典序最小。

之后再从右往左扫，若 s[i]!=t[i] 就修改 \(S\) 字符串，同理，可证得这样修改的字符串字典序最小。

#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 1e5+10;

string s1,s2;
int ans;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s1>>s2;
    int n=s1.length();
    seq(i,0,n-1){
        if(s1[i]!=s2[i]){
            ans++;                 //由于要修改的字母量为定值，所以优先统计
        }
    }
    cout<<ans<<"\n";
    seq(i,0,n-1){
        if(s1[i]-s2[i]>0){
            s1[i]=s2[i];
            cout<<s1<<"\n";       //无需存储，直接输出
        }
    }
    for(int i=n-1;i>=0;i--){
        if(s1[i]!=s2[i]){
            s1[i]=s2[i];
            cout<<s1<<"\n";
        }
    }
    return 0;
}