题解

题意分析

Soundex编码是一种将发音相似的单词归类的方法。题目要求实现Soundex编码规则，将输入的大写单词转换为对应的数字编码。编码规则包括：

1. 将特定字母转换为数字（如$B,F,P,V$转换为$1$）。
2. 忽略某些字母（如$A,E,I,O,U,H,W,Y$）。
3. 去除连续的相同数字（如$BB$编码为$1$而非$11$）。

解题思路

1. 字母分类：将字母按编码规则分组，每组对应一个数字。
2. 遍历输入单词：对每个字母，检查其所属的数字类别。
3. 去重处理：跳过与前一个编码数字相同的字母，避免连续重复数字。
4. 输出编码：将处理后的数字序列作为Soundex编码输出。

实现步骤

1. 初始化字母分组：使用集合（$set$）存储每组字母对应的数字类别。
2. 读取输入单词：逐行读取输入的大写单词。
3. 编码转换：
   • 遍历单词的每个字母。
   • 检查字母是否属于某个数字类别，若是则输出对应数字并记录当前数字。
   • 忽略不属于任何数字类别的字母。
4. 去重处理：跳过连续相同数字的字母。
5. 输出结果：完成遍历后输出编码结果。

代码注释

#include<iostream>
#include<stdio.h>
#include<string>
#include<set>
using namespace std;

int main()
{
    // 初始化字母分组，每组对应一个数字类别
    set<char> coll[7]; // coll[1]到coll[6]分别存储数字1到6对应的字母

    coll[1].insert('B'); // 数字1对应的字母
    coll[1].insert('F');
    coll[1].insert('P');
    coll[1].insert('V');

    coll[2].insert('C'); // 数字2对应的字母
    coll[2].insert('G');
    coll[2].insert('J');
    coll[2].insert('K');
    coll[2].insert('Q');
    coll[2].insert('S');
    coll[2].insert('X');
    coll[2].insert('Z');

    coll[3].insert('D'); // 数字3对应的字母
    coll[3].insert('T');

    coll[4].insert('L'); // 数字4对应的字母

    coll[5].insert('M'); // 数字5对应的字母
    coll[5].insert('N');

    coll[6].insert('R'); // 数字6对应的字母

    int i; // 循环变量
    int j; // 循环变量
    int tem; // 记录前一个编码数字
    string s; // 存储输入的单词

    while(cin>>s) // 逐行读取输入单词
    {
        tem = -1; // 初始化前一个编码数字为-1（表示无前驱）
        for(i = 0; i < s.length(); ++i) // 遍历单词的每个字母
        {
            for(j = 1; j <= 6; ++j) // 检查字母属于哪个数字类别
            {
                if(coll[j].find(s[i]) != coll[j].end()) // 如果字母在当前数字类别中
                {
                    if(tem != j) // 如果当前数字与前一个数字不同
                    {
                        cout<<j; // 输出数字
                        tem = j; // 更新前一个数字
                    }
                    break; // 跳出内层循环
                }
            }
            if(j == 7) // 如果字母不属于任何数字类别（忽略）
                tem = -1; // 重置前一个数字
        }
        cout<<endl; // 输出换行
    }
    return 0;
}

复杂度分析

• 时间复杂度：假设单词长度为$n$，每个字母最多检查$6$个数字类别，时间复杂度为$O(n \times 6)$，即$O(n)$。
• 空间复杂度：使用固定大小的集合存储字母分组，空间复杂度为$O(1)$。