[蓝桥杯]找到给定字符串中的不同字符

题目描述

在不考虑字符排列的条件下，对于相差只有一个字符的两个字符串，实现一个算法来识别相差的那个字符。要求如下：

1. 当传入的字符串为 aad 和 ad 时，结果为 a。

2. 当传入的字符串为 aaabccdd 和 abdcacade 时，结果为 e。

输入描述

输入两行字符串，长度均不超过 100。

输出描述:

输出一行，为相差的那个字符。

输入输出样例

示例

输入

aad
ad

输出

a

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 5726  |  总提交次数: 6103  |  通过率: 93.8%

难度: 中等   标签: 新手

方法思路

题目要求找出两个字符串中相差的那个字符（两个字符串长度相差1，且只相差一个字符）。最优解法是利用​​异或运算​​的性质：

复杂度分析

示例验证

1. ​​异或特性​​：相同字符异或结果为0，任何字符与0异或结果为本身。
2. ​​核心思路​​：将两个字符串的所有字符进行异或运算，成对出现的字符会相互抵消（结果为0），最终剩下的字符就是相差的那个字符。
3. ​​优势​​：时间复杂度为O(n)，空间复杂度O(1)，效率高且代码简洁。

   #include <iostream>
   #include <string>
   using namespace std;int main() {string s1, s2;getline(cin, s1);  // 读取第一行字符串getline(cin, s2);  // 读取第二行字符串// 检查输入是否为空（题目要求非空，但需处理None情况）if (s1.empty() || s2.empty()) {cerr << "TypeError: str1 or str2 cannot be None" << endl;return 1;}char result = 0;// 遍历s1所有字符进行异或for (char c : s1) {result ^= c;}// 遍历s2所有字符进行异或for (char c : s2) {result ^= c;}cout << result << endl;  // 输出相差的字符return 0;
   }

   代码解释

4. ​​输入处理​​：

   • 使用getline()读取两行字符串，确保包含空格也能正确处理。
   • 检查输入是否为空，若为空则抛出TypeError（符合题目要求）

5. ​​异或运算​​：

   • 初始化result = 0。
   • 遍历s1的每个字符，与result异或：相同字符会抵消（如'a' ^ 'a' = 0）。
   • 遍历s2的每个字符，再次与result异或：最终结果即为相差字符（因该字符只出现一次，无法被抵消）

6. ​​输出结果​​：

   • 直接输出result，即相差的字符。

7. ​​输入​​：aad 和 ad
   ​​计算过程​​：
   'a' ^ 'a' ^ 'd' ^ 'a' ^ 'd' = ('a' ^ 'a' ^ 'a') ^ ('d' ^ 'd') = 'a' ^ 0 = 'a'
   ​​输出​​：a（正确）

8. ​​输入​​：aaabccdd 和 abdcacade
   ​​输出​​：e（因e仅在第二个字符串中出现一次）

9. ​​时间复杂度​​：O(n)，仅需遍历两个字符串各一次。
10. ​​空间复杂度​​：O(1)，仅使用常量空间。