e589 - 11223 - O: dah dah dah!
題目描述
題目要求將給定的摩斯電碼序列解碼為可讀的英文訊息。摩斯電碼由點（.）、破折（-）和空格表示，點和破折代表短音和長音，空格分隔字母和單詞。題目提供了一個摩斯電碼到字符的映射表。
解題思路
程式碼的核心思想是模擬摩斯電碼的解碼過程。它首先定義了一個包含所有摩斯電碼及其對應字符的字串陣列。然後，程式碼逐組讀取輸入，並將每組輸入的摩斯電碼序列分割成字母。對於每個字母，程式碼將其摩斯電碼與陣列中的每個條目進行比較，如果找到匹配項，則輸出對應的字符。程式碼還處理了空格，將單個空格輸出為空格，多個空格輸出為單個空格。
複雜度分析
- 時間複雜度: O(T * N * M)，其中 T 是測試案例的數量，N 是每組輸入的長度，M 是摩斯電碼陣列的大小（53）。最壞情況下，程式碼需要遍歷整個輸入字串，並將每個摩斯電碼與陣列中的所有條目進行比較。
- 空間複雜度: O(1)，程式碼使用的額外空間是固定的，不隨輸入大小而變化。主要空間消耗來自於儲存摩斯電碼陣列，其大小是固定的。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string str[53] = {"A.-", "B-...", "C-.-.", "D-..", "E.", "F..-.", "G--.","H....", "I..", "J.---", "K-.-", "L.-..", "M--", "N-.", "O---","P.--.", "Q--.-", "R.-.", "S...", "T-", "U..-", "V...-", "W.--","X-..-", "Y-.--", "Z--..", "0-----", "1.----", "2..---", "3...--","4....-", "5.....", "6-....", "7--...", "8---..", "9----.","..-.-.-", ",--..--", "?..--..", "'.----.", "!-.-.--", "/-..-.","(-.--.", ")-.--.-", "&.-...", ":---...", ";-.-.-.", "=-...-","+.-.-.", "--....-", "_..--.-", "\".-..-.", "@.--.-."};
string a;
int T;
scanf("%d", &T);
getline(cin,a);
for (int t = 1; t <= T; ++t){
printf("Message #%d\n", t);
getline(cin,a);
a+=' ';
int al=a.length();
string tmp;
int i=0;
while(a[i]==' ')++i;
for (;i<al;++i){
bool space=0;
if (a[i] == ' '){
int tl=tmp.length();
if(tmp==" "){
cout << a[i];
break;
}
for(int j=0;j<53;++j){
if(tl!=str[j].length()-1)continue;
bool ans=1;
for(int k=1;k<str[j].length();++k){
if(tmp[k-1]!=str[j][k]){
ans=0;
break;
}
}
if(ans)
cout << str[j][0];
}
tmp.clear();
++i;
}
while(a[i]==' '){
if(space==0){
cout << " ";
space=1;
}
++i;
}
tmp+=a[i];
}
if(t!=T)
puts("\n");
else
puts("");
}
return 0;
}