alan23273850 的刷題筆記
d781: 00195 - Anagram
Tags: permutation
出處：https://zerojudge.tw/ShowProblem?problemid=d781
提交：https://zerojudge.tw/Submissions?problemid=d781&account=allllllan123456
問題：給你一個長度不超過 50 的字串，字串只會包含大小寫字母 (字元可能重複)，請你按照 AaBbCcDd…..YyZz 這樣子的字典順序依序印出字串中的這些字母重新打散之後的所有排列，並且注意到如果當下的字串已經在之前就出現過的話則不予印出。
解法：這題跟 d436 非常類似，差別在於沒有數字出現以及重新定義字母的大小順序。可以參考程式碼學習如何重新定義字元順序。
1#include <bits/stdc++.h>
2using namespace std;
3
4int len;
5char arr[50], num[50];
6
7void dfs(string ans) {
8 bool allUsed = true;
9 for (int i=0; i<len; i++)
10 if (num[i]) allUsed = false,
11 num[i]--, dfs(ans + arr[i]), num[i]++;
12 if (allUsed) cout << ans << '\n';
13}
14
15int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
16 int T; cin >> T;
17 while (T--) { cin >> arr;
18 len = strlen(arr); memset(num, 0, sizeof num);
19 sort(arr, arr + len, [](char a, char b) {
20 char c = a - ('a'-'A') * (a >= 'a');
21 char d = b - ('a'-'A') * (b >= 'a');
22 if (c == d) return a < b;
23 return c < d;
24 });
25 int j = 0; num[0] = 1;
26 for (int i=1; i<len; i++)
27 if (arr[i] == arr[j]) num[j]++;
28 else j++, arr[j] = arr[i], num[j] = 1;
29 arr[j+1] = 0; len = strlen(arr);
30 dfs("");
31 }
32 return 0;
33}