d781 - 00195 - Anagram
題目描述
題目要求對於給定的字串，產生所有可能的字串排列組合（Anagram），並按照字典序輸出。需要考慮大小寫的差異，且輸出不應包含重複的排列組合。
解題思路
本題的核心是產生字串的所有排列組合。可以使用 std::next_permutation 函數來實現。為了確保輸出的排列組合按照字典序遞增，需要先對輸入字串進行排序。此外，題目要求大小寫字母的比較順序為 A-Z, a-b, ... , Y-z，因此需要自定義一個比較函數 cmp 來處理大小寫的比較。
複雜度分析
- 時間複雜度: O(n! * n log n)，其中 n 是字串的長度。
next_permutation的平均時間複雜度為 O(n)，而產生所有排列組合的數量為 n!。 排序的複雜度為 O(n log n)。 - 空間複雜度: O(n)，主要用於儲存字串。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(char a, char b){
char la = tolower(a), lb = tolower(b);
if (la != lb)
return la < lb;
else
return a < b;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string a;
cin >> a;
while(cin >> a){
sort(a.begin(),a.end(),cmp);
do{
cout << a << "\n";
}while(next_permutation(a.begin(),a.end(),cmp));
}
}