ZeroJudge A224: 明明愛明明

迴文:一種修辭方式
通過詞語反復迴環使用,表達二者互相依存或彼此制約的關係,
如:「人人為我,我為人人」、「饒人不癡漢,癡漢不饒人」。

範例測資

範例輸入範例輸出
使用 EOF 收資料,一筆測試資料一行,包含許許多多但總數不超過 1000 個的大小寫英文字母和標點符號。
不可思議的是,裡面不會有任何空白字元。
如果重新安排順序後,有辦法讓這一堆英文字母變成迴文的話,輸出「yes !」,否則輸出「no…」。
注意,大寫和小寫字母視為相同,即 A 和 a 是一樣的,並且,請忽視所有非英文字母的字元。
ababa
bbaaa
Level
aaabbbcc
abcdefg
HowAreYouToday
A_man,_a_plan,_a_canal:_Panama.
yes !
yes !
yes !
no…
no…
no…
yes !

解題思路

因為題目的要求為「可重組」,所以就要使用迴文的定義來判斷字串是否可以組成一個迴文。在迴文中,每一個字元都是雙雙成對的,除非字串長度為奇數則最中間的字元為非成對出現。所以可以利用MAP來統計每一個字元所出現的次數,並且使用「isalpha(str[i])」和「tolower(str[i])」來判斷目前的字元是否是英文字母且強制將所有英文字母轉換為小寫來避免大小寫判斷問題。迴圈結束後從0到26跑一次For迴圈來確定每一個英文字母的MAP值都是偶數,如果有超過一個字母為非偶數的情況 (剛剛講到的中間字元非成對出現的狀況),則此字串不可變成迴文。

範例程式碼-ZeroJudge A224: 明明愛明明

#include <iostream>
#include <map>
using namespace std;

int main() {
    string str;
    while (cin >> str)
    {
        map<int, int>MAP;
        for (int i = 0; i<str.size(); i++)
        {
            if (isalpha(str[i])) MAP[tolower(str[i]) - 'a']++;
        }
        int count = 0;
        for (int i = 0; i<26; i++)
        {
            if (MAP[i] % 2 != 0) count += 1;
        }
        if (count > 1) cout << "no..." << endl;
        else cout << "yes !" << endl;
    }
}

//ZeroJudge A224
//Dr. SeanXD

發佈留言