题意

给定一个字符串str，和一组字符串

寻找在这组字符串中有多少个和str不直接相等，但包含的内容相等的(可以交换字母得到)

这组字符串中满足条件的按照字典序排序，求第k个是哪个字符

方法

朴素实现

本题要3个工作

1. 比较相等
2. 比较是否可以交换得到
3. 对给定字符串排序

我们分别如下实现

1. 朴素比较
2. 对两个字符串，一个辅助数组标记前一个字符是否匹配，遍历后一个字符串，在前一个字符串中找相同字符
3. 内置的sort排序

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define pb push_back

bool movable(const string &s0, const string &s1){ // s0 s1 是否能通过交换得到
  if(s0.size() != s1.size())return false;
  vector<bool> vis(s0.size(),false); // s0 是否匹配
  for(auto ch:s1){ // 枚举s1 的字符
    bool found = false;
    rep(i,0,s0.size()){  // 在s0中找没匹配过的相同字符
      if(vis[i])continue;
      if(s0[i] == ch){ // 找到对应字符进行匹配
        found = true;
        vis[i] = true;
        break;
      }
    }
    if(!found){
      return false;
    }
  }
  return true;
}

int main(){
  vector<string> ss = {};
  vector<string> sdict = {};
  int n;
  cin>>n;
  rep(i,0,n){
    string s;
    cin>>s;
    ss.pb(s);
  }
  string str;
  cin>>str;
  for(auto si:ss){
    if(si == str)continue; // 排除相等
    if(!movable(str,si))continue; // 不能交换得到
    sdict.pb(si);
  }
  sort(sdict.begin(),sdict.end()); // 字符串排序
  cout<<sdict.size()<<endl;
  int k;
  cin>>k;
  if(k<=sdict.size()){
    cout<< sdict[k-1]<<endl;
  }
  return 0;
}

复杂度分析

设 字典中字符串个数为$nn$n 字典的字符总长度为$\sum \mid s_i\mid \backslash sum\{|s\_i|\}$∑∣si​∣, 查询的str的长度为$mm$m,

时间复杂度:

读入的部分显然是$O(\sum \mid s_i\mid +m)O(\backslash sum\{|s\_i|\}+m)$O(∑∣si​∣+m)

对于每个字符的处理，使用字符和字典内的比较的复杂度最坏情况是$O\left(m{n}^2\right)O(mn^2)$O(mn2)

对于字符串排序，最坏是$O(m\cdot n\cdot log(n\left)\right)O(m\; \backslash cdot\; n\; \backslash cdot\; log(n))$O(m⋅n⋅log(n))

空间复杂度: 空间主要是存储字符串，每个字符串最多被存在两个位置,额外辅助数组最大长度和字符串长度相关，所以空间复杂度为$O(\sum \mid s_i\mid +m)O(\backslash sum\{|s\_i|\}+m)$O(∑∣si​∣+m)

利用字符串的内部排序后再比较

上面的第2点，我们可以优化

1. 如果两个字符串可以交换交换得到，那么当且仅当它们自身按字母排序后的两个字符串是相等的

对于第2点数学证明如下，

1. 每个字符串自身内部按照字母顺序排序是唯一的
2. 每个字符串与其自身内部按照字母顺序是可以相互转换的
3. 综上如果两个字符串可以交换字符得到，那么当且仅当它们自身按字母排序后的两个字符串是相等的

以样例为例

其中abc（本身和查找的字符串也相等，所以忽略）

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define pb push_back

string sortstr(string s){ // 字符串自身按字母排序
  sort(s.begin(),s.end());
  return s;
}

int main(){
  vector<string> ss = {};
  vector<string> sdict = {};
  int n;
  cin>>n;
  rep(i,0,n){
    string s;
    cin>>s;
    ss.pb(s);
  }
  string str;
  cin>>str;
  string t = sortstr(str);
  for(auto si:ss){
    if(si == str)continue; // 排除相等
    if(t != sortstr(si))continue; // 最小序和查找的最小序不等
    sdict.pb(si);
  }
  sort(sdict.begin(),sdict.end()); // 字符串排序
  cout<<sdict.size()<<endl;
  int k;
  cin>>k;
  if(k<=sdict.size()){
    cout<< sdict[k-1]<<endl;
  }
  return 0;
}

复杂度分析

设 字典中字符串个数为$nn$n 字典的字符总长度为$\sum \mid s_i\mid \backslash sum\{|s\_i|\}$∑∣si​∣, 查询的str的长度为$mm$m,

时间复杂度:

读入的部分显然是$O(\sum \mid s_i\mid +m)O(\backslash sum\{|s\_i|\}+m)$O(∑∣si​∣+m)

对于每个字符的处理，使用sort对字符内部排序，最坏情况是$O(\sum \mid s_i\mid \cdot log(\sum \mid s_i\mid \left)\right)O(\backslash sum\{|s\_i|\}\backslash cdot\; log(\backslash sum\{|s\_i|\}))$O(∑∣si​∣⋅log(∑∣si​∣)),

和查找字符串比较排序后的内容，所有位置比较一次，最差情况$O(\sum \mid s_i\mid )O(\backslash sum\{|s\_i|\})$O(∑∣si​∣)，

对于字符串排序，最坏是$m\cdot n\cdot log\left(n\right)m\; \backslash cdot\; n\; \backslash cdot\; log(n)$m⋅n⋅log(n)

空间复杂度: 空间主要是存储字符串，每个字符串最多被存在两个位置，所以空间复杂度为$O(\sum \mid s_i\mid +m)O(\backslash sum\{|s\_i|\}+m)$O(∑∣si​∣+m)