每一組輸入都有兩行不含空白且 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