公司起名测算网1518(公司起名测名打分测试)

2306. 公司命名

题目

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

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

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

示例 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/

本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 610798281@qq.com 举报,一经查实,本站将立刻删除。
如若转载,请注明出处:https://www.52mingliang.com/6623.html