ZeroJudge A275: 字串變變變

每一組輸入都有兩行不含空白ASCII 碼介於 33~126 之間的字串,請告訴我,經過適當的順序調整後,兩個字串會變得一模一樣嗎?

例如:「e83k」可以調整順序成「38ek」或「e3k8」等等共 15 種其他排列方式。

範例測資

範例輸入範例輸出
EOF 輸入,每筆一行字串,當讀到「STOP!!」時結束。
字串長度最長為 1000000 個字元。
如果兩個字串可以變得一樣,輸出「yes」,否則輸出「no」。
e83k
38ek
asdfghjkl;’
‘;lkjhgfdsa
1234
4521
SToP!!
stop!!
STOP!!
yes
yes
no
no

解題思路

本題需使用 cin優化/scanf 才不會TLE,另外收到兩組字串過後可以先判斷兩個字串的長度是否相同,如果不相同的話直接輸出no節省時間。可以使用For迴圈將每個字串中的字元做處理,使用一個 Map 存每個字元出現的次數。假設兩個字串的名稱叫做A和B,把A的每個字元的Map值做+1、把B的每個字元的Map值做-1。之後使用 for (auto it:Map) 來將 Map 中的資料做判斷,使用 for (auto it:MAP) 的時候 it 這個變數會變成一個 pair,所以只要判斷 it.second 是否為0,如果有不是0的話就輸出 no 並將 For迴圈 break 掉節省時間,如果都是0的話就輸出yes。

範例程式碼-ZeroJudge A275: 字串變變變

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string a;
    while (cin >> a && a != "STOP!!")
    {
        string b;
        cin >> b;
        if (a.length() != b.length()) cout << "no\n";
        else
        {
            map<char, int>MAP;
            for (int i = 0; i<a.length(); i++)
            {
                MAP[a[i]]++;
                MAP[b[i]]--;
            }
            bool yes = true;
            for (auto it:MAP)
            {
                if (it.second != 0)
                {
                    cout << "no\n";
                    yes = false;
                    break;
                }
            }
            if (yes) cout << "yes\n";
        }
    }
}

//ZeroJudge A275
//Dr. SeanXD

發佈留言