e524 - 106 彰雲嘉區複賽 - Q4 變位字判斷
題目描述
題目要求判斷兩行文字是否為變位字。變位字是指兩段文字包含的字母相同，但字母的排列順序不同。忽略大小寫和標點符號，只考慮字母。
解題思路
程式首先讀取測試案例的數量 n。對於每個測試案例，程式讀取兩行字串 a 和 b。然後，程式將字串 a 和 b 中的所有字母轉換為小寫，並去除非字母字元，儲存在新的字串 aa 和 bb 中。接著，程式對 aa 和 bb 進行排序。最後，程式比較排序後的字串 aa 和 bb。如果它們相等，則輸出 1，表示 a 和 b 是變位字；否則，輸出 0。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是字串的長度。這是因為排序操作的時間複雜度是 O(n log n)。
- 空間複雜度: O(n)，因為需要額外的空間來儲存轉換後的字串
aa和bb。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
string a,b;
cin >> n;
getline(cin,a);
while(n--){
getline(cin,a);
getline(cin,b);
int al=a.length(),bl=b.length();
string aa,bb;
for(int i=0;i<al;++i){
if(a[i]>='a'&&a[i]<='z')
aa+=a[i];
else if(a[i]>='A'&&a[i]<='Z')
aa+=a[i]+'a'-'A';
}
for(int i=0;i<bl;++i){
if(b[i]>='a'&&b[i]<='z')
bb+=b[i];
else if(b[i]>='A'&&b[i]<='Z')
bb+=b[i]+'a'-'A';
}
sort(aa.begin(),aa.end());
sort(bb.begin(),bb.end());
if(aa!=bb)cout << "0\n";
else
cout << "1\n";
}
}