CF518A Vitaly and Strings

这是一道 简单的字符串处理 题。

解决本题首先要了解 字典序 是什么:

字典序是指按照单词出现在字典的顺序进行排序的方法。
在英文字典中,排列单词的顺序是先按照第一个字母以升序排列(即 $ a $、$ b $、$ c $ $ …… $ $ z $ 的顺序);如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,$ sigh $ 和 $ sight $),那么把短者排在前。

通过思考我们可以发现从后往前可以极大的简化题目,设 $ next $ 为下一个序列需要修改的英文字母,将 $ next $ 设为字符串 $ s $ 或 $ t $ 的长度 $ -1 \ \ $ (两个字符串的长度相同),将 $ next $ 加 $ 1 $ 使它变成下一个字符,如果 $ s [next] > 122$,就将 $ next-- $,使 $ s[next] = a $ 。

循环结束后,如果下一个序列的字典序大于等于 $ t $ 的字典序,就输出 $ No \ such \ string $,否则输出 $ s $ 。

Code:

#include <iostream>
#include <cstring>

int main()
{
    std::string s, t;
    std::cin >> s >> t;
    int next = s.length() - 1;
    s[next]++;
    while (s[next] > 122) {
        s[next] = 'a';
        s[--next]++;
    }
    if (s >= t) std::cout << "No such string" << std::endl;
    else std::cout << s << std::endl;
    return 0;
}
Last modification:October 10th, 2021 at 03:03 pm
赠人玫瑰,手有余香。您的赞赏是对我最大的支持!