2306. 公司命名

题目

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：

0. 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
1. 交换 ideaA 和 ideaB 的首字母。
2. 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
3. 否则，不是一个有效的名字。

返回 不同 且有效的公司名字的数目。

示例 1：

 输入：ideas = ["coffee","donuts","time","toffee"]
 输出：6
 解释：下面列出一些有效的选择方案：
 - ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
 - ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
 - ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
 - ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
 - ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
 - ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
 因此，总共有 6 个不同的公司名字。
 
 下面列出一些无效的选择方案：
 - ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
 - ("time", "toffee")：在原数组中存在交换后形成的两个名字。
 - ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。

示例 2：

 输入：ideas = ["lack","back"]
 输出：0
 解释：不存在有效的选择方案。因此，返回 0 。

提示：

• 2 <= ideas.length <= 5 * 10^4
• 1 <= ideas[i].length <= 10
• ideas[i] 由小写英文字母组成
• ideas 中的所有字符串 互不相同

解题思路

方法一：枚举计数

假设 ideaA 是已知的，ideaA 的首字母为 x。对于 ideas 中首字母为 y 的 ideaB ：

• 如果 ideaA 的首字母由 x 改为 y后，不在名字列表中；
• 并且，如果 ideaB 的首字母由 y 改为 x后，也不在名字列表中；

则 ideaA 和 ideaB 可以组成一个有效的公司名字。

对于每个 ideaA 如何求到符合要求的 ideaB 的数量呢？

我们可以记 cnt[x][y] 表示可以把首字母从 x 改成 y 以后不在名字列表中的字符串数量，这可以通过枚举所有 ideas 中的字符串和首字母可以变成的所有字符（字符集中的所有字符），来统计 cnt[x][y] 的数量。

有了 cnt 数组，我们就可以求得每个 ideaA 首字母由 x 变成 y，符合要求的 ideaB 的数量，即 cnt[y][x]。

所有 ideaA 所对应的符合要求的 ideaB 的数量之和，即为答案。

复杂度分析

• 时间复杂度：，其中 是字符集大小。
• 空间复杂度：。

方法二：分组枚举

• 首先，按每个名字的首字母进行分组；
• 对于 A 组中的名字 ideaA 和 B 组中的名字 ideaB，只要 ideaA[1:] 和 ideaB[1:] 其中有一个在另一个分组中存在，则 ideaA 和 ideaB 就无法互换首字母，否则可以互换；
• 设 A 组和 B 组的交集大小为 m，则这两个分组可以组成合法答案数为：

• 遍历所有的分组对，累加合法答案数。

复杂度分析

• 时间复杂度：，其中 是字符集大小。
• 空间复杂度：。

方法三：分组枚举

• 按照除首字母外名字字符串剩余部分分组，形式：<除首字母外剩余部分，首字母list>。
• 设 ideaA 的首字母为 i，ideaB 的首字母为 j，两者要能够组成有效公司名字，那么 i 不能出现在 ideaB 所属组的首字母中，且 j 也不能出现在 ideaA 所属组的首字母中，即 有 i 无 j 可以和 无 j 有 i 的名字互换。
• 定义 cnt[i][j] 表示首字母不为 i 为 j 的分组个数。
• 遍历所有分组，统计 cnt。
• 同时在遍历时，亦一起向答案累加可以与当前分组（有 j 无 i）组成有效公司名字的组数（有 i 无 j）。
• 由于没有考虑两个字符串的顺序，最后需要把答案乘 2，表示 A+B 和 B+A 两种组合。

复杂度分析

• 时间复杂度：，其中 是字符集大小。
• 空间复杂度：。

代码

class Solution {
    public long distinctNames(String[] ideas) {
        int n = ideas.length;
        Set<String> set = Arrays.stream(ideas).collect(Collectors.toSet());
        int[][] cnt = new int[26][26];
        boolean[][] flag = new boolean[n][26];
        for (int i = 0; i < n; i++) {
            int x = ideas[i].charAt(0) - 'a';
            for (int y = 0; y < 26; y++) {
                String str = (char)(y + 'a') + ideas[i].substring(1);
                if (!set.contains(str)) {
                    cnt[x][y]++;
                    flag[i][y] = true;
                }
            }
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            int x = ideas[i].charAt(0) - 'a';
            for (int y = 0; y < 26; y++) {
                if (flag[i][y]) {
                    ans += cnt[y][x];
                }
            }
        }
        return ans;
    }
}

class Solution {
    public long distinctNames(String[] ideas) {
        var group = new Set[26];
        for (int i = 0; i < 26; i++) {
            group[i] = new HashSet<String>();
        }
        for (String idea : ideas) {
            group[idea.charAt(0) - 'a'].add(idea.substring(1));
        }
        long ans = 0;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < i; j++) {
                long m = 0;
                for (var s : group[i]) {
                    if (group[j].contains(s)) {
                        m++;
                    }
                }
                ans += (group[i].size() - m) * (group[j].size() - m);
            }
        }
        return ans * 2;
    }
}

class Solution {
    public long distinctNames(String[] ideas) {
        Map<String, Integer> groups = new HashMap<>();
        for (String idea : ideas) {
            String t = idea.substring(1);
            groups.put(t, groups.getOrDefault(t, 0) | (1 << (idea.charAt(0) - 'a')));
        }
        long ans = 0;
        int[][] cnt = new int[26][26]; // 表示组中首字母不包含i但包含j的组的个数
        for (int mask : groups.values()) {
            for (int i = 0; i < 26; i++) {
                if ((mask & (1 << i)) == 0) { // 当前首字母不为i
                    for (int j = 0; j < 26; j++) {
                        if ((mask & (1 << j)) > 0) { // 首字母为j
                            cnt[i][j]++; // 累积每个分组中首字母不包含i但包含j的组个数
                        }
                    }
                } else { // 当前分组首字母为i
                    for (int j = 0; j < 26; j++) {
                        if ((mask & (1 << j)) == 0) { // 首字母不为j
                            ans += cnt[i][j]; // 累加首字母为j不为i的分组数
                        }
                    }
                }
            }
        }
        return ans * 2;
    }
}

参考

分组 + 枚举首字母 + 互补思想：https://leetcode.cn/problems/naming-a-company/solution/by-endlesscheng-ruz8/

题目链接：https://leetcode.cn/problems/naming-a-company/