查找兄弟单词（HJ20）

查找兄弟单词 题解

题目描述

定义一个字符串 s 的”兄弟单词”为：将 s 重新排序后得到的与原字符串不同的新字符串。

给定 n 个字符串和另一个字符串 x，需要：

1. 统计这 n 个字符串中，有多少个是 x 的”兄弟单词”
2. 将这些兄弟单词按字典序排序，输出第 k 个

输入：

• n：字符串个数
• n 个字符串
• x：目标字符串
• k：要查找的第 k 小的兄弟单词

输出：

• 第一行：兄弟单词数量
• 第二行：第 k 个兄弟单词（如果存在）

示例：

• 输入：3 abc bca cab abc 1
• 输出：

  2
  bca

---

解法

问题类型：字符串匹配 + 排序

思路：

1. 判断两个字符串是否互为兄弟单词：字母排序后相同，且不是同一个单词
2. 遍历所有字符串，筛选出 x 的兄弟单词
3. 按字典序排序，输出第 k 个

代码

line = input().split()
n = int(line[0])
arr = line[1: n + 1]
x = line[n + 1]
x_sort = sorted(x)
k = int(line[-1])

res = []

for s in arr:
    if sorted(s) == x_sort and s != x:
        res.append(s)

res.sort()
print(len(res))
if k <= len(res):
    print(res[k - 1])

时间复杂度：O(n × m log m)，m 为字符串长度（最坏10）
空间复杂度：O(n)

注意：兄弟单词必须满足两个条件：①字母组成相同 ②不是同一个单词