ABC370C Word Ladder

原题链接：C - Word Ladder

Tag：模拟

题目描述

给你两个由小写英文字母组成的字符串 \(S\) 和 \(T\) 。 其中， \(S\) 和 \(T\) 的长度相等。

设 \(X\) 为空数组，重复下面的操作直到 \(S\) 等于 \(T\) ：

• 更改 \(S\) 中的一个字符，并将 \(S\) 追加到 \(X\) 的末尾。

找出这样得到的元素个数最少的字符串数组 \(X\) 。如果有多个元素个数相同的数组， 请找出其中按词典顺序最小的一个。

数据说明：

\(1 \leq |S|,|T| \leq 100\)

分析

因为题目要我们构造的是字典序最小的， 所以我们第一次从前面开始遍历， 看能不能把对应字符变小， 如果可以的话就变。

第二次遍历就从后面开始， 这一次直接把目标字符串和当前字符串的所有不一样的位置都修改掉， 记录答案输出就可以了。

代码实现

void NeverSayNever() {
    string str1,str2;
    cin >> str1 >> str2;
    int n = str1.size();
    vector<string> ans;
    for (int i = 0; i < n ; ++i) {
        if(str2[i] < str1[i]){
            str1[i] = str2[i];
            ans.push_back(str1);
        }
    }
    for (int i = n; i >= 0 ; --i) {
        if(str2[i] != str1[i]){
            str1[i] = str2[i];
            ans.push_back(str1);
        }
    }
    cout << ans.size() << endl;
    for(auto &x : ans) cout << x << endl;
}

日志

本页面创建于 2024/09/09 11:14