找出卧底问题解析

问题理解

我们需要统计在 $n$ 个字符串中，有多少个字符串在不区分大小写的情况下等于 "WOHEYEZHI"。每个字符串代表一个队员的特点，符合这个特点的就是卧底。

关键思路

1. 不区分大小写比较：需要将输入的字符串统一转换为大写（或小写）后再进行比较
2. 目标字符串：固定目标为 "WOHEYEZHI"
3. 统计匹配数量：遍历所有字符串，统计与目标字符串匹配的数量

算法选择

• 将每个输入字符串转换为大写形式
• 与目标字符串 "WOHEYEZHI" 进行精确匹配
• 统计匹配成功的次数

代码实现

#include <bits/stdc++.h>  // 包含常用标准库
using namespace std;

int main(){
    int n;  // 队员数量
    cin >> n;  // 读取队员数量
    
    int cnt = 0;  // 计数器，记录卧底数量
    string t = "WOHEYEZHI";  // 目标字符串（卧底特征）
    
    // 处理每个队员的特点字符串
    for(int i = 0; i < n; i++){
        string s;  // 当前队员的特点字符串
        cin >> s;  // 读取字符串
        
        string ls;  // 用于存储转换为大写的字符串
        // 将原字符串的每个字符转换为大写
        for(int i = 0; i < s.size(); i++){
            ls += toupper(s[i]);  // 转换为大写并添加到新字符串
        }
        
        // 检查转换后的字符串是否与目标字符串匹配
        if (ls == t){
            cnt++;  // 如果是卧底，计数器加1
        }
    }
    
    cout << cnt;  // 输出卧底总数
    return 0;  // 程序正常结束
}

算法分析

1. 时间复杂度：$O(n \times m)$，其中 $n$ 是字符串数量，$m$ 是字符串平均长度
   • 每个字符串需要遍历一次进行大小写转换
   • 字符串比较的时间复杂度为 $O(m)$
2. 空间复杂度：$O(m)$，需要额外的空间存储转换后的字符串

优化建议

可以直接在比较时进行大小写转换，避免创建新字符串：

// 替代方案：直接比较，不创建新字符串
bool isMatch = true;
if(s.length() != t.length()) {
    isMatch = false;
} else {
    for(int j = 0; j < s.length(); j++) {
        if(toupper(s[j]) != t[j]) {
            isMatch = false;
            break;
        }
    }
}
if(isMatch) cnt++;

注意事项

• 题目保证字符串长度不超过20，因此直接创建新字符串的方法是可接受的
• 使用 toupper() 函数确保大小写不敏感比较
• 目标字符串 "WOHEYEZHI" 是固定的，不需要处理大小写变化