d400 - A-排列組合
題目描述
題目要求生成給定字符串的所有排列組合，但需要滿足一些額外的條件。這些條件以成對的字母形式給出，表示第一個字母必須在第二個字母之前出現。輸出前 10 個滿足條件的排列組合，如果沒有找到任何滿足條件的排列組合，則輸出 "NANJ你唬我"。
解題思路
程式碼使用迴圈生成所有可能的排列組合，並使用 next_permutation 函數來實現。對於每個排列組合，程式碼會檢查它是否滿足所有給定的條件。條件的檢查通過一個布林陣列 k 來實現，該陣列記錄每個字母是否已經出現過。如果一個字母出現過，則檢查它是否在所有必須在其之前的字母之前出現。如果所有條件都滿足，則輸出該排列組合。程式碼還限制輸出的排列組合數量為 10 個。
首先，程式碼將輸入的字符串中的每個字符映射到一個唯一的整數 ID，以便更容易地檢查條件。然後，程式碼對字符串進行排序，以便 next_permutation 函數可以生成所有可能的排列組合。對於每個排列組合，程式碼檢查它是否滿足所有給定的條件。如果滿足，則輸出該排列組合。
複雜度分析
- 時間複雜度: O(n! * m)，其中 n 是字符串的長度，m 是條件的數量。生成所有排列組合需要 O(n!) 的時間，對於每個排列組合，檢查條件需要 O(m) 的時間。
- 空間複雜度: O(n + m)，其中 n 是字符串的長度，m 是條件的數量。程式碼使用一個映射來存儲字符到 ID 的映射，以及一個布林陣列來記錄每個字母是否已經出現過。
程式碼
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int n,m;
bool lit[28][28];
char x,y;
string s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
while(n--){
cin >> s >> m;
for(int i=0;i<27;++i){
for(int j=0;j<27;++j){
lit[i][j]=0;
}
}
int id=1;
map <int,int> mp;
map <int,int> pm;
for(int i=0;i<s.size();++i){
if(mp[s[i]-'a']==0){
mp[s[i]-'a']=id;
pm[id]=s[i]-'a';
++id;
}
}
for(int i=0;i<s.size();++i){
s[i]=mp[s[i]-'a']+'a';
}
for(int i=0;i<m;++i){
cin >> x >> y;
lit[x-'a'][y-'a']=1;
}
sort(s.begin(),s.end());
int ok=0;
do{
bool k[28]={0},ac=1;
for(int i=0;i<s.size()&∾++i){
if(k[(pm[s[i]-'a'])]==0){
for(int j=0;j<26&∾++j){
if(lit[(pm[s[i]-'a'])][j]&&k[j]){
ac=0;
//cout << "del==\n";
}
}
}
k[(pm[s[i]-'a'])]=1;
}
if(ac){
for(int i=0;i<s.size();++i){
cout << (char)(pm[s[i]-'a']+'a');
}
cout << "\n";
ok++;
}
if(ok>=10)break;
}while(next_permutation(s.begin(),s.end()));
if(ok==0){
cout << "NANJ你唬我\n";
}
}
}