不改变元音和辅音的相对位置的单词排列？

介绍

单词排列（Anagram）是指将一个单词或者短语的字母重新排列，组成一个新的单词或者短语，但是字母的种类和数量不变。在这个问题中，我们希望找到一个单词列表，其中每个单词的元音和辅音字母的相对位置都不改变。

方法

1. 计数排序法

计数排序法是一个非常高效的排序算法，用来对给定的整数数组进行排序。这种算法是通过统计数组中每个元素出现的次数来排序的。我们可以通过这种方法来解决这个问题。首先，我们可以定义一个字符数组，用来存储两个额外的字符串：一个是原字符串中的元音字符，一个是原字符串中的辅音字符。然后，我们可以使用计数排序的方法来排序这两个字符串。计数排序的时间复杂度是O(n)，这个解决方案的时间复杂度也是O(n)。 以下是代码实现：

#include <iostream>
#include <string>
using namespace std;
const int MAX = 30005;
int n;
string str[MAX], ans[MAX];
int cnt[2][30];
bool check(char c)
{
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> str[i];
    }
    for(int i = 1; i <= n; i++)
    {
        int len = str[i].length();
        int a = 0, b = 0;
        for(int j = 0; j < len; j++)
        {
            if(check(str[i][j]))
            {
                cnt[0][++a] = str[i][j] - 'a' + 1;
            }
            else
            {
                cnt[1][++b] = str[i][j] - 'a' + 1;
            }
        }
        for(int j = 1; j <= a; j++)
        {
            ans[i] += (char)(cnt[0][j] + 'a' - 1);
        }
        for(int j = 1; j <= b; j++)
        {
            ans[i] += (char)(cnt[1][j] + 'a' - 1);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            if(ans[i] == ans[j])
            {
                cout << str[i] << " " << str[j] << endl;
            }
        }
    }
    return 0;
}

2. 用哈希表计数法

这种解决方案的另一个方法是使用哈希表来计数。这种解决方案的思想是将一个单词的元音和辅音字符分别分配到散列桶中，然后检查是否有其它单词具有相同的元音和辅音字符。以下是代码实现：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
typedef pair<int, int> pii;
unordered_set<pii> h;
int n;
bool check(char c)
{
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
pii getHash(string str)
{
    pii res = {0, 0};
    int len = str.length();
    for(int i = 0; i < len; i++)
    {
        if(check(str[i]))
        {
            res.first += 1;
        }
        else
        {
            res.second += 1;
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        pii p = getHash(s);
        if(h.count(p))
        {
            cout << *(h.find(p)) << " " << s << endl;
        }
        h.insert(p);
    }
    return 0;
}

总结

这个问题是一个有趣的问题，因为许多单词都有相同的元音和辅音字母。这个问题可以用计数排序法或者哈希表计数法来解决。另外，对于面试者来说，应该具备熟练掌握哈希表的能力，因为哈希表可以解决许多实际问题和算法问题。