力扣刷题——2306. 公司命名

根据题意，很容易就能想到用哈希表来做。先写一个最简单的暴力，完全就是模拟。

long long distinctNames(vector<string> &ideas)
{
    int n = ideas.size();
    unordered_map<string, int> um;
    for (int i = 0; i < n; i++)
    {
        um[ideas[i]] = 1;
    }
    long long res = 0;
    for (int i = 0; i < n - 1; i++)
    {
        string &a = ideas[i];
        for (int j = i + 1; j < n; j++)
        {
            string &b = ideas[j];
            if (a[0] == b[0])
                continue;

            if (um.find(b[0] + a.substr(1, a.size() - 1)) != um.end() || um.find(a[0] + b.substr(1, b.size() - 1)) != um.end())
                continue;
            res++;
        }
    }
    res *= 2;
    return res;
}

但是不出意外肯定会超时，假如在哈希表里存后缀，就能减少构造新string的次数，看看行不行。

long long distinctNames(vector<string> &ideas)
{
    int n = ideas.size();
    unordered_map<string, vector<int>> um;
    for (int i = 0; i < n; i++)
    {
        if (um.find(ideas[i].substr(1, ideas[i].size() - 1)) != um.end())
            um[ideas[i].substr(1, ideas[i].size() - 1)][ideas[i][0] - 'a'] = 1;
        else
        {
            um[ideas[i].substr(1, ideas[i].size() - 1)] = vector<int>(26, 0);
            um[ideas[i].substr(1, ideas[i].size() - 1)][ideas[i][0] - 'a'] = 1;
        }
    }
    long long res = 0;
    for (int i = 0; i < n - 1; i++)
    {
        string &a = ideas[i];
        for (int j = i + 1; j < n; j++)
        {
            string &b = ideas[j];
            if (a[0] == b[0])
                continue;

            if (um[a.substr(1, a.size() - 1)][b[0] - 'a'] || um[b.substr(1, b.size() - 1)][a[0] - 'a'])
                continue;
            res++;
        }
    }
    res *= 2;
    return res;
}

上述的优化将哈希表改造成了存后缀和首字母的一个结构，这样在原来比对过程中就不需要用重载的+号运算符构造新string，以此提升速度。但是仍然会超时，应该是调用哈希表的次数太多了，并且哈希表中内容也很多。
再次分析一下问题，当进行判断是否能够组成一个新店名的时候,其实可以不用通过调用哈希表来计算。
举例子说，当ideas = {"coffee", "donuts", "time", "toffee"}，依次将后缀加入哈希表中，同时再维护一个交集数组和首字母数组。
在遍历完donuts时，coffee只能选择 donuts。换句话说，只有1种选择，即首字母c和首字母d选择1次
在遍历完time时，coffee能选择 donuts和time，同时donuts还能选择time。这时，就有3种选择，c能选择d和t各1次，d能选择t1次
在遍历完toffee时，出现了不能选的情况，如果不剔除的话，情况应该是：
选择1：c能选择t2次
选择2：c能选择d1次
选择3：d能选择t2次
通过后缀offee在字典中的信息，可以知道产生了交集。首先，因为coffee和time，导致了c与t的选择存在相同后缀，选择1减少1次；接着，因为coffee和toffee，导致了c与t的选择存在相同后缀，选择1减少1次。
在交集数组的维护过程中，不用考虑相同首字母的情况做特别的维护，因为这个可以在最终计算里直接避免，因此有实现如下：

long long distinctNames(vector<string> &ideas)
{
    int n = ideas.size();
    vector<int> heads(26, 0);
    vector<vector<int>> intersection(26, vector<int>(26, 0));
    unordered_map<string, vector<int>> um;
    for (int i = 0; i < n; i++)
    {
        int head = ideas[i][0] - 'a';
        heads[head]++;
        if (um.find(ideas[i].substr(1)) != um.end())
        {
            um[ideas[i].substr(1)][head] = 1;
        }
        else
        {
            um[ideas[i].substr(1)] = vector(26, 0);
            um[ideas[i].substr(1)][head] = 1;
        }
        for (int j = 0; j < 26; j++)
        {
            if (um[ideas[i].substr(1)][j] == 1)
            {
                intersection[head][j]++;
                intersection[j][head]++;
            }
        }
    }
    long long res = 0;
    for (int i = 0; i < 25; i++)
    {
        for (int j = i + 1; j < 26; j++)
        {
            res += (long long)(heads[i] - intersection[i][j]) * (heads[j] - intersection[i][j]);
        }
    }
    res *= 2;
    return res;
}

还能做进一步的优化，用一个int来表示一个后缀是否存在某个首字母的情况：

long long distinctNames(vector<string> &ideas)
{
    int n = ideas.size();
    vector<int> heads(26, 0);
    vector<vector<int>> intersection(26, vector<int>(26, 0));
    unordered_map<string, int> um;
    for (int i = 0; i < n; i++)
    {
        int head = ideas[i][0] - 'a';
        heads[head]++;
        um[ideas[i].substr(1)] = um[ideas[i].substr(1)] | (1 << head);
        for (int j = 0; j < 26; j++)
        {
            if ((um[ideas[i].substr(1)] >> j) & 1)
            {
                intersection[head][j]++;
                intersection[j][head]++;
            }
        }
    }
    long long res = 0;
    for (int i = 0; i < 25; i++)
    {
        for (int j = i + 1; j < 26; j++)
        {
            res += (long long)(heads[i] - intersection[i][j]) * (heads[j] - intersection[i][j]);
        }
    }
    res *= 2;
    return res;
}