a131 - 00739 - Soundex Indexing
題目描述
題目要求實作 Soundex 索引演算法，將輸入的名字轉換為 Soundex 碼。Soundex 碼是一個四位字串，第一位是名字的第一個字母，後三位是根據特定規則編碼的數字，不足四位則用 '0' 補齊。
解題思路
程式首先讀取輸入的名字。然後，它將名字中的字母轉換為對應的數字代碼，根據 Soundex 規則。接著，程式會移除相鄰的重複數字，並保留第一個字母。最後，程式將結果補齊到四位，並輸出名字及其對應的 Soundex 碼。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為程式需要遍歷字串一次來進行編碼，以及一次來移除重複的數字。
- 空間複雜度: O(1)，因為程式使用的額外空間是固定的，不隨輸入大小而變化。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string a;
cout << " NAME SOUNDEX CODE\n";
while(cin >> a){
cout << " " << a;
int tmpl=a.length();
while(tmpl<25){
cout << " ";
++tmpl;
}
string ans;
ans+=a[0];
int it=1;
char tmp;
for(int i=0,al=a.length();i<al;++i){
if(a[i]=='B'||a[i]=='P'||a[i]=='F'||a[i]=='V'){
a[i]='1';
}
else if(a[i]=='C'||a[i]=='S'||a[i]=='K'||a[i]=='G'||a[i]=='J'||a[i]=='Q'||a[i]=='X'||a[i]=='Z'){
a[i]='2';
}
else if(a[i]=='D'||a[i]=='T'){
a[i]='3';
}
else if(a[i]=='L'){
a[i]='4';
}
else if(a[i]=='M'||a[i]=='N'){
a[i]='5';
}
else if(a[i]=='R'){
a[i]='6';
}
else{
a[i]='0';
}
}
tmp=a[0];
for(int i=1,al=a.length();i<al;++i){
if(a[i]!='0'&&a[i]!=tmp){
ans+=a[i];
}
tmp=a[i];
}
int ansl=ans.length();
if(ansl<4){
cout << ans;
while(ansl<4){
cout << '0';
++ansl;
}
cout << "\n";
}
else{
for(int i=0;i<4;++i){
cout << ans[i];
}
cout << "\n";
}
}
cout << " END OF OUTPUT\n";
}