e268 - 11233 - Deli Deli
題目描述
題目要求根據給定的規則，將單詞轉換為複數形式。如果單詞在提供的詞典中，則直接輸出詞典中的複數形式。否則，根據單詞結尾的字母進行判斷，並應用相應的規則生成複數形式。規則如下：
- 如果單詞以子音字母結尾的 "y" 結尾，則將 "y" 替換為 "ies"。
- 如果單詞以 "o", "s", "x", "ch", "sh" 結尾，則在字尾添加 "es"。
- 否則，在字尾添加 "s"。
解題思路
程式首先讀取一個詞典，將單數形式和複數形式儲存在 map 中。然後，對於每個輸入單詞，程式首先檢查它是否存在於詞典中。如果存在，則輸出詞典中對應的複數形式。如果不存在，則根據題目描述的規則，判斷單詞的結尾字母，並生成相應的複數形式，然後輸出。
複雜度分析
- 時間複雜度: O(N + M * K)，其中 N 是詞典的大小，M 是輸入單詞的數量，K 是單詞的平均長度。詞典的建立需要 O(N) 的時間，對於每個輸入單詞，判斷是否在詞典中需要 O(log N) 的時間，生成複數形式需要 O(K) 的時間。
- 空間複雜度: O(N)，其中 N 是詞典的大小。空間主要用於儲存詞典。
程式碼
#include <iostream>
#include <map>
using namespace std;
map <string ,string> sp;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
string a,b;
while(n--){
cin >> a >> b;
sp[a]=b;
}
while(m--){
cin >> a;
if(sp.find(a)==sp.end()){
int al=a.length()-1;
if(a[al]=='y'&&a[al-1]!='a'&&a[al-1]!='e'&&a[al-1]!='i'&&a[al-1]!='o'&&a[al-1]!='u'){
a[al]='i';
a+="es";
cout << a << "\n";
}
else if(a[al]=='o'||a[al]=='s'||a[al]=='x'||(a[al]=='h'&&(a[al-1]=='c'||a[al-1]=='s'))){
a+="es";
cout << a << "\n";
}
else{
a+="s";
cout << a << "\n";
}
}
else{
cout << sp[a] << "\n";
}
}
}