HJ81. 字符串字符匹配
题目描述
判断短字符串 S 中的所有字符是否都在长字符串 T 中出现。
输入格式
- 第 1 行：短字符串
- 第 2 行：长字符串
输出格式
若短串每个字符都在长串中出现，输出 true，否则输出 false。
示例
示例 1
输入：
bc
abc
输出：
true
示例 2
输入：
aDc
abc
输出：
false
解题思路
第一步：理解问题本质
判断短串的每个字符是否是长串的字符集合的子集。只需关心"字符是否出现"，与顺序、次数无关。
第二步：暴力解法
对短串的每个字符，遍历长串逐个比较。O(len(S) × len(T))，简单但可优化。
第三步：最优解法（集合）
先把长串转成集合 set(T)，得到 O(1) 的成员查询，再用 all 检查短串每个字符：
long_set = set(long_s)
result = all(ch in long_set for ch in short_s)
print("true" if result else "false")
完整代码实现
算法可视化 · 逐帧回放这道题的代码5 帧 · 录制输入
import sys
def solve():
data = sys.stdin.buffer.read().split()
short_s = data[0].decode()
long_s = data[1].decode()
long_set = set(long_s)
result = all(ch in long_set for ch in short_s)
print("true" if result else "false")
if __name__ == "__main__":
solve()
示例推演
以示例 2（短串 aDc，长串 abc）为例：
- 长串集合
{'a','b','c'} - 检查
a∈ 集合 ✓ - 检查
D∈ 集合 ✗（区分大小写，D≠d）
结果：false。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 双重循环 | O(S·T) | O(1) | 简单但慢 |
| 集合查询 | O(S+T) | O(T) | 最优 |
易错点总结
1. 大小写敏感
本题区分大小写，D 与 d 不同。用集合时必须精确匹配。
2. 用集合会去重
set(long_s) 自动去重，正好符合"只关心是否出现"的语义，不影响判断。
3. 空输入处理
若短串为空，all([]) 返回 True；本题通常短串非空，但需注意边界。
扩展思考
- 集合去重的思想也可用于"判断两个字符串是否由相同字符构成"。
- 若还需记录字符数量，可用
collections.Counter。