我已经解决了以下问题，但仍需要提高性能：
我有N个字。对于每个有效的 i，单词 i 由 字符串 Di 仅包含小写元音，即字符 'a'， 'e'， "我"、"o"、"u"。
(无序)单词对的总数是多少，当 串联起来，它们包含所有的元音？
我的C++代码使用位数组来表示单词中存在的元音。 然后，我通过组合它们的位数组来检查所有字符串对，查看是否设置了所有元音位。 我通过将组合与位数组"完整"进行比较来做到这一点，该数组的所有位都设置为与元音相对应：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t; // number of different test cases
while(t--)
{
int n; // number of strings
cin>>n;
int con_s[n];
for(int i=0;i<n;i++)
{
string s;
cin>>s;
con_s[i]=0; // converting vowels present in string into a bit array
for(int j=0;j<s.length();j++)
{
con_s[i] = con_s[i] | (1<<(s[j]-'a'));
}
}
int complete = 0; // bit array corresponding to all possible vowels
complete = (1<<('a'-'a')) | (1<<('e'-'a')) | (1<<('i'-'a')) | (1<<('o'-'a')) | (1<<('u'-'a'));
// cout<<complete;
int count = 0;
for(int i=0;i<n-1;i++) // check the pairs
{
for(int j=i+1;j<n;j++)
{
if((con_s[i] | con_s[j])==complete)count++;
}
}
cout<<count<<"n";
}
return 0;
}
尽管位数组使用非常快的位操作，但在具有较大的输入字符串集时，我的算法似乎不够高效。 任何人都可以提出有效的解决方案吗？
其他信息
测试用例：
Input:
1
3
aaooaoaooa
uiieieiieieuuu
aeioooeeiiaiei
Result: 2
解释： 2 对(1 和 2)和(2 和 3)在连接时包含所有 5 个元音，而对(1 和 3)不符合标准，因为连接不包含"u"。因此，结果为 2。
约束：
1≤T≤1,000
1≤N≤105
1≤|Di|≤1,000 for each valid i
the sum of all |D_i| over all test cases does not exceed 3⋅107
假设您有大量的字符串。 您的算法将比较它们之间的所有字符串，这是一个可怕的迭代次数。
彻底改进：
新方法
构建一个映射，将有序的唯一元音字符串(例如"ae")与找到的所有字符串的列表相关联，这些字符串恰好包含这些唯一元音，无论重复次数和顺序如何。例如：
ao -> aaooaoaooa, aoa, aaooaaooooooo (3 words)
uie -> uiieieiieieuuu, uuuuiiiieeee (2 words)
aeio -> aeioooeeiiaiei (1 word)
当然，这是很多字符串，因此在代码中，您将使用位图而不是有序的唯一元音字符串。 另请注意，您不想生成组合字符串的列表，而只想生成它们的计数。 因此，您不需要所有字符串出现的列表，而只需要维护与位图匹配的字符串计数：
16385 -> 3
1048848 -> 2
16657 -> 1
然后查看映射现有索引之间的获胜组合，就像您所做的那样。对于较大的字符串列表，映射索引列表要小得多，因此这将是一个重大改进。
对于每个获胜组合，将第一个字符串列表的大小乘以第二个字符串列表的大小以增加计数。
16385 1048848 is complete -> 3 x 2 = 6 combinations
1048848 16657 is complete -> 2 x 1 = 2 combinations
---
8 potential combinations
有什么改进？
这些组合是通过分析 3x2 位图而不是查看对应于唯一字符串的 6x5 位图找到的。 如果字符串数量较多，则增益显著增加一个数量级。
更笼统地说，由于您有 5 个 wovel 并且必须至少有一个，因此您最多只能有2<<5-1个 31 个不同的位图，因此最多 C(31,2) 是 46531*30930
可能的实现：
map<int, int> mymap;
int n;
cin>>n;
for(int i=0;i<n;i++) {
string s;
cin>>s;
int bm=0;
for(int j=0;j<s.length();j++)
bm |= (1<<(s[j]-'a'));
mymap[bm]++;
}
int complete = (1<<('a'-'a')) | (1<<('e'-'a')) | (1<<('i'-'a')) | (1<<('o'-'a')) | (1<<('u'-'a'));
int count = 0;
int comparisons = 0;
for (auto i=mymap.begin(); i!=mymap.end(); i++) {
auto j=i;
for(++j;j!=mymap.end();j++) {
comparisons++;
if((i->first | j->first)==complete) {
count += i->second * j->second;
cout << i->first <<" "<<j->first<<" :"<<i->second<<" "<<j->second<<endl;
}
}
}
auto special = mymap.find(complete); // special case: all strings having all letters
if (special!=mymap.end()) { // can be combined with themselves as well
count += special->second * (special->second -1) / 2;
}
cout<<"Result: "<<count<<" (found in "<<comparisons<<" comparisons)n";
包含 4 个示例的在线演示(仅包含所有字母的字符串、您的初始示例、我上面的示例以及包含更多字符串的示例)