a224 - 明明愛明明
題目描述
題目要求判斷給定的字串是否能重新排列成迴文。字串只包含大小寫英文字母和標點符號，需要忽略非英文字母，並將大小寫字母視為相同。
解題思路
首先，將輸入字串轉換為小寫，並移除所有非英文字母。然後，統計每個字母出現的次數。如果字串長度為偶數，則所有字母的出現次數都必須是偶數才能形成迴文。如果字串長度為奇數，則只能有一個字母的出現次數為奇數，其餘字母的出現次數必須是偶數。程式碼中，使用一個貪婪的策略，將配對的字母替換為 '0'，最後檢查是否所有字母都已配對。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是字串的長度。這是因為程式碼使用了嵌套迴圈來查找配對的字母。
- 空間複雜度: O(1)，因為使用的額外空間是固定的，不隨輸入字串的長度變化。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
string a,b;
bool c=false;
while(cin >> a){
b.clear();
for(int i=0;i<a.length();i++){
if(a[i]>=65&&a[i]<=90){
b+=a[i]+32;
}
else if(a[i]>=97&&a[i]<=122){
b+=a[i];
}
}
c=true;
if(b.length()%2==0){
for(int i=0;i<b.length();i++){
for(int j=i+1;j<b.length();j++){
if(b[i]==b[j]&&b[i]!='0'&&b[j]!='0'){
b[i]='0';
b[j]='0';
}
}
}
for(int i=0;i<b.length();i++){
if(b[i]!='0'){
c=false;
break;
}
}
}
else{
int d=true;
for(int i=0;i<b.length();i++){
for(int j=i+1;j<b.length();j++){
if(b[i]==b[j]&&b[i]!='0'&&b[j]!='0'){
b[i]='0';
b[j]='0';
}
}
}
for(int i=0;i<b.length();i++){
if(b[i]!='0'){
if(d==false){
c=false;
break;
}
d=false;
}
}
}
if(c==true){
cout << "yes !" << endl;
}
else{
cout << "no..." << endl;
}
}
}