刷题笔记合集🔗

匿名信

问题描述

电视剧《分界线》里面有一个片段，男主为了向警察透露案件细节，且不暴露自己，于是将报刊上的字减下来，剪拼成匿名信。
现在又一名举报人，希望借鉴这种手段，使用英文报刊完成举报操作。
但为了增加文章的混淆度，只需满足每个单词中字母数量一致即可，不关注每个字母的顺序。
解释：单词 允许通过单词 进行替代。
报纸代表 newspaper，匿名信代表 anonymousLetter，求报纸内容是否可以拼成匿名信。

输入格式

第一行输入 newspaper 内容，包括 个字符串，用空格分开。

第二行输入 anonymousLetter 内容，包括 个字符串，用空格分开。

newspaper 和 anonymousLetter 的字符串由小写英文字母组成，且每个字母只能使用一次；
newspaper 内容中的每个字符串字母顺序可以任意调整，但必须保证字符串的完整性（每个字符串不能有多余字母）。
，

输出格式

如果报纸可以拼成匿名信返回 true，否则返回 false。

样例输入

ab cd
ab

ab ef
aef

ab bcd ef
cbd fe

ab bcd ef
cd ef

样例输出

true

false

true

false

数据范围

题解

这道题的核心是判断报纸上的单词是否能用来组成匿名信。需要注意的是，单词内字母顺序不重要，重要的是字母组成相同。

解题思路很直观：

1. 对报纸中的每个单词，我们将其字母排序，这样就可以忽略字母顺序的影响
2. 然后统计报纸中每个排序后单词出现的次数
3. 再对匿名信中的每个单词做同样的处理（排序）
4. 检查匿名信中的每个排序后单词是否在报纸中存在并且数量足够

这种解法的巧妙之处在于使用"字符排序"来处理"字母顺序不重要"这个条件。例如，单词"on"和"no"排序后都是"no"，这样我们就能轻松判断它们是否可以互相替代。

这个策略的时间复杂度是 O(n)，其中 n 是报纸和匿名信中单词的总数。我们只需要遍历每个单词一次，将其排序然后进行对比。虽然排序本身的复杂度是 O(k log k)，其中 k 是单词的平均长度，但因为题目中单词长度相对较短，可以视为常数时间。

这个时间复杂度对于题目给定的数据范围（最多 10^4 个单词）来说是完全可接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
news = input().split()
letter = input().split()

# 检查报纸是否可以拼成匿名信的函数
def can_form_letter(news, letter):
    # 统计报纸中各种单词的数量
    # 对每个单词先排序，这样就忽略了字母顺序
    word_count = {}
    for word in news:
        # 对单词字母排序
        sorted_word = ''.join(sorted(word))
        word_count[sorted_word] = word_count.get(sorted_word, 0) + 1
    
    # 检查匿名信中的每个单词是否能在报纸中找到
    for word in letter:
        # 对单词字母排序
        sorted_word = ''.join(sorted(word))
        
        # 检查这个排序后的单词是否在报纸中存在且有足够数量
        if sorted_word in word_count and word_count[sorted_word] > 0:
            word_count[sorted_word] -= 1  # 使用一次后减少计数
        else:
            # 找不到匹配的单词，无法拼成
            return "false"