[2306] 公司命名

回溯

超时了

Javascript

var distinctNames = function (ideas) {
    let ans = 0;
    let map = ideas.reduce((map, val, i) => {
        map.set(val, i);
        return map;
    }, new Map());
    backtrack(new Map());
    return ans;

    function backtrack(path) {
        if (path.size === 2) {
            const [a, b] = path.keys();
            if (!map.has(`${b[0]}${a.slice(1)}`) && !map.has(`${a[0]}${b.slice(1)}`)) {
                ans++;
            }
            return;
        }
        for (const name of ideas) {
            if (!path.has(name)) {
                path.set(name, 1);
                backtrack(path);
                path.delete(name);
            }
        }
    }
};

后缀树

details

解释：

交换 "coffee" 和 "donuts" 的首字母生成的两个名称是 "doffee" 和 "conuts"。这两个名称都不是已有的创意。
交换 "coffee" 和 "time" 的首字母生成的两个名称是 "toffee" 和 "cime"。"toffee" 是已有的创意，因此这组创意不可行。
交换 "donuts" 和 "time" 的首字母生成的两个名称是 "tonuts" 和 "dime"。这两个名称都不是已有的创意。

类似地，其他的可行组合可以生成 6 个新名称。

解题思路

要解决这个问题，我们需要考虑如何有效地检测创意的前缀和后缀的交换，且保证生成的新名称不在原有创意中。

步骤：

按首字母分类：将 ideas 中的创意按首字母进行分类。
检测可能的交换：遍历每个类别中的创意，将它们的首字母与其他类别中的创意进行交换，形成新的名称。
检查重复：确保交换后的两个名称都不在原有创意中。
计数新名称：统计可以生成的新名称的数量。

代码实现

function distinctNames(ideas) {
    // 按首字母分类，将所有创意分成 26 类
    const groups = Array.from({ length: 26 }, () => new Set());

    for (let idea of ideas) {
        const firstLetterIdx = idea.charCodeAt(0) - 'a'.charCodeAt(0);
        groups[firstLetterIdx].add(idea.slice(1)); // 只存储后缀
    }

    let result = 0;

    // 逐对比较不同首字母的组
    for (let i = 0; i < 25; i++) {
        for (let j = i + 1; j < 26; j++) {
            let mutual = 0;

            // 找到两个不同首字母组中的相同后缀
            for (let idea of groups[i]) {
                if (groups[j].has(idea)) {
                    mutual++;
                }
            }

            // 新生成的名字是有效的组合数
            let validPairCount = (groups[i].size - mutual) * (groups[j].size - mutual);
            result += 2 * validPairCount; // 每对可以生成两个新名字
        }
    }

    return result;
}

代码讲解

按首字母分类：我们创建一个数组 groups，每个元素是一个集合，用于存储所有以该字母开头的创意的后缀。例如，"coffee" 会被存储为 groups[2].add("offee")。
计算相同后缀：遍历每一对不同首字母的组，查找它们之间相同的后缀，并记录这些相同后缀的数量。
计算有效的组合：如果组 i 和组 j 有 mutual 个相同的后缀，那么这两个组可以生成的有效新名称的数量是 (groups[i].size - mutual) * (groups[j].size - mutual)。
结果加倍：因为每一对组可以生成两个新名称，所以我们将有效组合数乘以 2。

时间复杂度

按首字母分类：O(n)，其中 n 是 ideas 中的创意数量。
遍历组和计算新名称：由于我们最多有 26 个首字母组，所以遍历每对不同的组需要 O(26 * 26) 次，即常数时间复杂度。每次比较组中的后缀可能需要 O(n) 时间。

因此，总的时间复杂度为 O(n)，适用于较大的输入规模。