PAT A1050：String Subtraction（哈希）

Python高阶函数，就是高！

本文作者：MowChan · 发布日期：2021/01/14 · 阅读时长：1 分钟

题目内容

Given two strings $S1$ and $S2$, $S=S1−S2$ is defined to be the remaining string after taking all the characters in $S2$ from $S1$. Your task is simply to calculate $S1−S2$ for any given strings. However, it might not be that simple to do it fast.

Input Specification:

Each input file contains one test case. Each case consists of two lines which gives $S1$ and $S2$, respectively. The string lengths of both strings are no more than $10^4$. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.

Output Specification:

For each test case, print $S1−S2$ in one line.

Sample Input:

They are students.
aeiou

Sample Output:

Thy r stdnts.

题目要点

本题 20 分，主要难点在时间复杂度的优化。使用 Python 的高阶函数和迭代器可以非常简单地解决，如果用 C/C++ 应当考虑用哈希表的方式判断要减去的字符。

AC 源代码

s1 = input()
s2 = input()
print(''.join(filter(lambda x: x not in s2, s1)))

使用 Python 简单清晰，各个测试点用时均在50ms左右，用时较少。