查找兄弟单词（HJ20）

查找兄弟单词 题解

题目描述

https://www.nowcoder.com/share/jump/5832603751775927842238

定义一个字符串 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)

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