定义一个字符串 s 的“兄弟单词”为:将 s 重新排序后得到的与原字符串不同的新字符串。 现在,对于给定的 n 个字符串 s_1, s_2, ..., s_n 和另一个单独的字符串 x ,你需要解决两个问题: 统计这 n 个字符串中,有多少个是 x 的“兄弟单词”(注意,这 n 个字符串可能有重复,重复字符串分别计数); 将这 n 个字符串中 x 的“兄弟单词”按字典序从小到大排序,输出排序后的第 k 个兄弟单词(从 1 开始计数)。特别地,如果不存在,则不输出任何内容。 【名词解释】 从字符串的第一个字符开始逐个比较,直至发现第一个不同的位置,比较这个位置字符的字母表顺序,字母序较小的字符串字典序也较小;如果比较到其中一个字符串的结尾时依旧全部相同,则较短的字符串字典序更小。
在一行上依次输入: 一个整数 n (1 ≤ n ≤ 10^3) 代表字符串的个数; n 个长度为 1 ≤ length(s_i) ≤ 10 ,仅由小写字母构成的字符串 s_1, s_2, ..., s_n ; 一个长度为 1 ≤ length(x) ≤ 10 ,仅由小写字母构成的字符串 x ; 一个整数 k (1 ≤ k ≤ n) 代表要查找的第 k 小的兄弟单词的序号。
第一行输出一个整数,代表给定的 n 个字符串中, x 的“兄弟单词”的数量; 第二行输出一个字符串,代表将给定的 n 个字符串中 x 的“兄弟单词”按字典序排序后的第 k 小兄弟单词。特别地,如果不存在,则不输出任何内容(完全省略第二行)。
3 abc bca cab abc 1
2 bca
3 a aa aaa a 1
0
考点:字符串 · 排序
数据规模 n ≤ 1e3 | 限制 1 秒 / 32MB | 标准输入输出
推荐方向:排序
先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。
思路框架(排序 通法 · 非本题专属)
实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。
复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)
该范式的通法易错点
对照本题
样例 1:输入 3 abc bca cab abc 1 → 输出 2 / bca
在这个样例中, x 的兄弟单词为 "acb" 、 "bac" 、 " orangebca " 、 " orangecab " 、 "cba" 。其中,标橙色的两个字符串存在于所给定的 n 个字符串中。第 1 小的兄弟单词为 "bca" 。
样例 2:输入 3 a aa aaa a 1 → 输出 0
在这个样例中,按照定义,字符串 "a" 没有兄弟单词。
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:华为机试编程模拟题2。