2306-公司命名

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

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

  1. 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
  2. 交换 ideaA 和 ideaB 的首字母。
  3. 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（ 串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
  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 * 104
  • 1 <= ideas[i].length <= 10
  • ideas[i] 由小写英文字母组成
  • ideas 中的所有字符串 互不相同

本题 视频讲解 已出炉，欢迎点赞三连~

提示 1

什么情况下得到的新名字不会在 ideas 中？

提示 2

按照除去首字母的子串 ideas}[i][1:] 分组，记录每组的首字母有哪些。

提示 3

我们不能选两个在同一组的字符串。那么考虑选两个分属不同组的字符串，这两个字符串需要满足什么要求？

提示 4

设 idea}_A 的首字母为 i，idea}_B 的首字母为 j。那么 i 不能出现在 idea}_B 所属组的首字母中，且 j 也不能出现在 idea}_A 所属组的首字母中。

提示 5

没有头绪？对于这类字符串问题，可以尝试枚举所有小写字母。

尝试枚举 i 和 j。我们需要统计什么？

提示 6

定义 cnt}[i][j] 表示组中首字母不包含 i 但包含 j 的组的个数。枚举每个组，统计 cnt，同时枚举该组的首字母 i 和不在该组的首字母 j，答案即为 cnt}[i][j] 的累加值。

简单来说就是「有 i 无 j」可以和「无 i 有 j」的字符串互换。

由于我们是一次遍历所有组，没有考虑两个字符串的顺序，最后需要把答案乘 2，表示 A+B 和 B+A 两种字符串的组合。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        group = defaultdict(int)
        for s in ideas:
            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))
        ans = 0
        cnt = [[0] * 26 for _ in range(26)]
        for mask in group.values():
            for i in range(26):
                if mask >> i & 1 == 0:
                    for j in range(26):
                        if mask >> j & 1:
                            cnt[i][j] += 1
                else:
                    for j in range(26):
                        if mask >> j & 1 == 0:
                            ans += cnt[i][j]
        return ans * 2
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public long distinctNames(String[] ideas) {
        var group = new HashMap<String, Integer>();
        for (var s : ideas) {
            var t = s.substring(1);
            group.put(t, group.getOrDefault(t, 0) | 1 << (s.charAt(0) - 'a'));
        }
        var ans = 0L;
        var cnt = new int[26][26];
        for (var mask : group.values())
            for (var i = 0; i < 26; i++)
                if ((mask >> i & 1) == 0) {
                    for (var j = 0; j < 26; j++)
                        if ((mask >> j & 1) > 0) ++cnt[i][j];
                } else {
                    for (var j = 0; j < 26; j++)
                        if ((mask >> j & 1) == 0) ans += cnt[i][j];
                }
        return ans * 2;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    long long distinctNames(vector<string> &ideas) {
        unordered_map<string, int> group;
        for (auto &s : ideas)
            group[s.substr(1)] |= 1 << (s[0] - 'a');
        long ans = 0L;
        int cnt[26][26] = {};
        for (auto &[_, mask] : group)
            for (int i = 0; i < 26; i++)
                if ((mask >> i & 1) == 0) {
                    for (int j = 0; j < 26; j++)
                        if (mask >> j & 1) ++cnt[i][j];
                } else {
                    for (int j = 0; j < 26; j++)
                        if ((mask >> j & 1) == 0) ans += cnt[i][j];
                }
        return ans * 2;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func distinctNames(ideas []string) (ans int64) {
	group := map[string]int{}
	for _, s := range ideas {
		group[s[1:]] |= 1 << (s[0] - 'a')
	}
	cnt := [26][26]int{}
	for _, mask := range group {
		for i := 0; i < 26; i++ {
			if mask>>i&1 == 0 {
				for j := 0; j < 26; j++ {
					if mask>>j&1 > 0 {
						cnt[i][j]++
					}
				}
			} else {
				for j := 0; j < 26; j++ {
					if mask>>j&1 == 0 {
						ans += int64(cnt[i][j])
					}
				}
			}
		}
	}
	return ans * 2
}

第二种实现方式是根据首字母分组。

对于 A 组中的字符串 s，如果 B 组中存在字符串 t，使得 s[1:]=t[1:]，那么 s 无法与 B 组中的任意字符串互换首字母，否则可以互换。对于 B 组同理。

设 A 组和 B 组交集的大小为 m，则这两个组可以组成的合法答案数为

2\cdot(|A|-m)\cdot(|B|-m)

其中 |A| 表示集合 A 的大小，|B| 表示集合 B 的大小。

遍历所有组对，累加答案。

注：相比上面的写法，这种写法会让 Python 跑的飞快，但是其他语言并无太大区别。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        group = defaultdict(set)
        for s in ideas:
            group[s[0]].add(s[1:])
        ans = 0
        for a, b in combinations(group.values(), 2):
            m = len(a & b)
            ans += (len(a) - m) * (len(b) - m)
        return ans * 2
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public long distinctNames(String[] ideas) {
        var group = new Set[26];
        for (var i = 0; i < 26; i++) 
            group[i] = new HashSet<String>();
        for (var s : ideas) 
            group[s.charAt(0) - 'a'].add(s.substring(1));
        var ans = 0L;
        for (var i = 1; i < 26; ++i)
            for (var j = 0; j < i; ++j) {
                var m = 0;
                for (var s : group[i])
                    if (group[j].contains(s)) ++m;
                ans += (long) (group[i].size() - m) * (group[j].size() - m);
            }
        return ans * 2;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long distinctNames(vector<string> &ideas) {
        unordered_set<string> group[26];
        for (auto &s : ideas)
            group[s[0] - 'a'].emplace(s.substr(1));
        long ans = 0L;
        for (int i = 1; i < 26; ++i)
            for (int j = 0; j < i; ++j) {
                int m = 0;
                for (auto &s : group[i])
                    m += group[j].count(s);
                ans += (long) (group[i].size() - m) * (group[j].size() - m);
            }
        return ans * 2;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func distinctNames(ideas []string) (ans int64) {
	group := [26]map[string]bool{}
	for i := range group {
		group[i] = map[string]bool{}
	}
	for _, s := range ideas {
		group[s[0]-'a'][s[1:]] = true
	}
	for i, a := range group {
		for _, b := range group[:i] {
			m := 0
			for s := range a {
				if b[s] {
					m++
				}
			}
			ans += int64(len(a)-m) * int64(len(b)-m)
		}
	}
	return ans * 2
}

第三种实现方式结合了上面两种写法，在遍历 ideas 的同时，计算上面写法中的交集大小 m。

具体地，按照除去首字母的子串 ideas}[i][1:] 分组，记录每组的首字母，同时统计字符 i 无法与多少个字符 j 开头的字符串交换。

[sol3-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        group = defaultdict(int)
        size = [0] * 26
        bad = [[0] * 26 for _ in range(26)]
        for s in ideas:
            i = ord(s[0]) - ord('a')
            s = s[1:]
            mask = group[s]
            group[s] |= 1 << i
            size[i] += 1
            for j in range(26):
                if mask >> j & 1:
                    bad[i][j] += 1  # 统计 i 无法与多少个 j 开头的字符串交换
                    bad[j][i] += 1  # 统计 j 无法与多少个 i 开头的字符串交换
        ans = 0
        for i, b in enumerate(bad):
            for j, m in enumerate(b[:i]):
                ans += (size[i] - m) * (size[j] - m)
        return ans * 2
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public long distinctNames(String[] ideas) {
        var group = new HashMap<String, Integer>();
        var size = new int[26];
        var bad = new int[26][26];
        for (var s : ideas) {
            var i = s.charAt(0) - 'a';
            s = s.substring(1);
            var mask = group.getOrDefault(s, 0);
            group.put(s, mask | 1 << i);
            ++size[i];
            for (var j = 0; j < 26; ++j)
                if ((mask >> j & 1) > 0) {
                    ++bad[i][j]; // 统计 i 无法与多少个 j 开头的字符串交换
                    ++bad[j][i]; // 统计 j 无法与多少个 i 开头的字符串交换
                }
        }
        var ans = 0L;
        for (var i = 1; i < 26; i++)
            for (var j = 0; j < i; j++)
                ans += (long) (size[i] - bad[i][j]) * (size[j] - bad[i][j]);
        return ans * 2;
    }
}
[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    long long distinctNames(vector<string> &ideas) {
        unordered_map<string, int> group;
        int size[26] = {};
        int bad[26][26] = {};
        for (auto &s: ideas) {
            int i = s[0] - 'a';
            auto t = s.substr(1);
            int mask = group[t];
            group[t] |= 1 << i;
            ++size[i];
            for (int j = 0; j < 26; ++j)
                if (mask >> j & 1) {
                    ++bad[i][j]; // 统计 i 无法与多少个 j 开头的字符串交换
                    ++bad[j][i]; // 统计 j 无法与多少个 i 开头的字符串交换
                }
        }
        long ans = 0L;
        for (int i = 1; i < 26; i++)
            for (int j = 0; j < i; j++)
                ans += (long) (size[i] - bad[i][j]) * (size[j] - bad[i][j]);
        return ans * 2;
    }
};
[sol3-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func distinctNames(ideas []string) (ans int64) {
	group := map[string]int{}
	size := [26]int{}
	bad := [26][26]int{}
	for _, s := range ideas {
		i := s[0] - 'a'
		mask := group[s[1:]]
		group[s[1:]] |= 1 << i
		size[i]++
		for j := 0; j < 26; j++ {
			if mask>>j&1 > 0 {
				bad[i][j]++ // 统计 i 无法与多少个 j 开头的字符串交换
				bad[j][i]++ // 统计 j 无法与多少个 i 开头的字符串交换
			}
		}
	}
	for i, b := range bad {
		for j, m := range b[:i] {
			ans += int64(size[i]-m) * int64(size[j]-m)
		}
	}
	return ans * 2
}
 Comments
On this page
2306-公司命名