🔗 UVA-11233 Deli Deli

tags: `模擬(Simulation)` `雜湊表(Hash Table)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定 $n$ 組單數和複數的對應，再給定 $m$ 個單數，依照以下規則輸出其複數形式：

若單數型態在給定的對應中，直接輸出對應的複數形式。
若單數以子音字母接"y"結尾，以"ies"取代"y"。
若單數以"o", “s”, “ch”, “sh”, “x"結尾，則在字尾多加上"es”。
其他情況，直接在字尾加上"s"。

LuckyCat 的中文翻譯

思路：模擬(Simulation)、雜湊表(Hash Table)

用雜湊表(Hash Table) 儲存單數和複數的對應，之後依照題目給定的規則輸出即可。

複雜度分析

時間複雜度： $O((n+m) \cdot k)$ ，其中 $k$ 為最長的字串長度。
空間複雜度： $O(n \cdot k)$ 。

n, m = map(int, input().split())
mp = dict()
for _ in range(n):
    a, b = input().split()
    mp[a] = b
for _ in range(m):
    s = input()
    n = len(s)
    if s in mp:
        print(mp[s])
    elif n > 1 and s[-1] == "y" and s[-2] not in "aeiou":
        print(s[:-1] + "ies")
    elif s[-1] in "osx" or s[-2:] in ["ch", "sh"]:
        print(s + "es")
    else:
        print(s + "s")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    string a, b, s;
    cin >> n >> m;
    map<string, string> mp;
    while (n--) {
        cin >> a >> b;
        mp[a] = b;
    }
    while (m--) {
        cin >> s;
        int k = s.size();
        if (mp.find(s) != mp.end())
            cout << mp[s] << endl;
        else if (k > 1 && s[k-1] == 'y' && s[k-2] != 'a' && s[k-2] != 'e' && s[k-2] != 'i' && s[k-2] != 'o' && s[k-2] != 'u') 
            cout << s.substr(0, k - 1) + "ies" << endl;
        else if (s[k-1] == 'o' || s[k-1] == 's' || s[k-1] == 'x' || (k > 1 && s[k-1] == 'h' && (s[k-2] == 'c' || s[k-2] == 's')))
            cout << s + "es" << endl;
        else
            cout << s + "s" << endl;
    }
    return 0;
}