旧键盘坏键识别：用 Set 做成员判断 + 去重，顺序靠遍历保留

题目给两行输入：

• 第一行：应该输入的文字（期望串）
• 第二行：实际输入的文字（实际串）

因为旧键盘坏了某些键，所以在敲击期望串时，对应字符不会出现在实际串里。目标是找出肯定坏掉的那些键，并按要求输出：

1. 按发现顺序输出（也就是从左到右扫描期望串，第一次发现某个坏键就立刻输出）
2. 字母只输出大写
3. 每个坏键只输出一次

---

import java.util.Scanner;
import java.util.HashSet;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
        String str1 = in.nextLine();
        Scanner sc2 = new Scanner(System.in);
        String str2 = in.nextLine();
        func(str1,str2);
        }
        }
         public static void func(String str1,String str2){
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        HashSet<Character> setStr2 = new HashSet<>();
        for(int i = 0;i<str2.length();i++){
            setStr2.add(str2.charAt(i));
        }
        HashSet<Character> setBrokens = new HashSet<>();
        for(int i = 0;i<str1.length();i++){
            if(!setStr2.contains(str1.charAt(i)) && !setBrokens.contains(str1.charAt(i))){
                setBrokens.add(str1.charAt(i));
                System.out.print(str1.charAt(i));
            }
    }
}
    }
    

1. 思路拆解：这题要解决三个小问题

问题 A：大小写怎么处理？

题目要求字母只输出大写，因此最省事的方式就是：

• 把两个字符串都转成大写，再统一比较

这样 'a' 和 'A' 都被当成 'A'，输出也天然满足要求。

str1 = str1.toUpperCase();
str2 = str2.toUpperCase();

问题 B：如何快速判断“某字符有没有在实际串里出现过”？

这里最适合用 HashSet<Character>：
把实际串所有字符放进 set，之后对每个字符查询 contains 都是平均 O(1)。

HashSet<Character> setStr2 = new HashSet<>();
for(int i = 0;i<str2.length();i++){
    setStr2.add(str2.charAt(i));
}

setStr2 的语义很明确：

实际输入里出现过的所有字符集合。

问题 C：如何做到“只输出一次，还要按发现顺序”？

关键点是：HashSet 本身不保序，所以不能靠 set 来输出顺序；顺序必须来自“扫描期望串的顺序”。

因此我的策略是：

• 从左到右扫描期望串 str1

• 遇到某个字符 c：

  • 如果 c 不在 setStr2 里 ⇒ 它没在实际串出现过 ⇒ 是坏键候选
  • 还要再判断 c 是否已经输出过 ⇒ 用另一个 set 来去重

• 第一次发现就输出，同时加入“已输出集合”

对应代码：

HashSet<Character> setBrokens = new HashSet<>();
for(int i = 0;i<str1.length();i++){
    char c = str1.charAt(i);
    if(!setStr2.contains(c) && !setBrokens.contains(c)){
        setBrokens.add(c);
        System.out.print(c);
    }
}

这里 setBrokens 的作用就是：

记录已经输出过的坏键，防止重复输出。

而“按发现顺序”来自于：
我是在遍历 str1 的过程中遇到就立刻输出，这个顺序天然就是题目要的顺序。

---

2. 用示例走一遍（把逻辑对齐题意）

输入：

• 期望：7_This_is_a_test
• 实际：_hs_s_a_es

转大写：

• 期望：7_THIS_IS_A_TEST
• 实际：_HS_S_A_ES

建立 setStr2（实际出现过的字符）：
{ '_', 'H', 'S', 'A', 'E' }（以及其它实际串里有的字符）

然后扫描期望串：

• '7' 不在 setStr2 ⇒ 输出 7
• '_' 在 setStr2 ⇒ 跳过
• 'T' 不在 ⇒ 输出 T
• 'H' 在 ⇒ 跳过
• 'I' 不在 ⇒ 输出 I
• 后面再次遇到 'T'，但 setBrokens 已有 T ⇒ 不再输出

最终输出 7TI，与示例一致。

---

3. 复杂度分析

设 n = str1.length，m = str2.length，都 ≤ 80。

• 建立 setStr2：O(m)
• 扫描 str1：O(n)，每次 contains 平均 O(1)
• 总体时间：O(n + m)
• 额外空间：两个集合，最多存 80 个字符 ⇒ O(1)（严格说是 O(字符集大小)）

---

4. 代码里的小问题与建议（不影响核心思路，但值得修）

4.1 输入部分多建了一个 Scanner（而且没用）

原代码里写了：

Scanner sc2 = new Scanner(System.in);
String str2 = in.nextLine();

sc2 没有被使用，而且重复创建 Scanner 也没必要。只用一个 Scanner in 就够了。

4.2 while(hasNextLine) 读两行时要小心“最后一行缺失”的情况

题目保证有两行，所以可以更直接写：

String str1 = in.nextLine();
String str2 = in.nextLine();
func(str1, str2);

如果保留循环读多组数据，也最好每次确认第二行存在：

while(in.hasNextLine()){
    String str1 = in.nextLine();
    if(!in.hasNextLine()) break;
    String str2 = in.nextLine();
    func(str1, str2);
}

（不过在 PAT/牛客这类题里通常输入就两行，不需要循环。）

---

总结

这题的关键不在字符串操作，而在把需求拆成三个结构化目标：

1. 统一大小写：对齐比较规则与输出规则
2. 快速判断缺失：用 setStr2 记录实际出现过的字符
3. 去重 + 保序输出：用 setBrokens 去重，但顺序靠扫描期望串时“发现即输出”

一旦把“成员判断”和“去重”交给 Set，再把“顺序”交给遍历过程，这题就会变得非常干净、非常稳。