class Solution {
public:
long long distinctNames(vector<string>& ideas) {
}
};
2306. 公司命名
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。ideaA 和 ideaB 的首字母。ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。返回 不同 且有效的公司名字的数目。
示例 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 * 1041 <= ideas[i].length <= 10ideas[i] 由小写英文字母组成ideas 中的所有字符串 互不相同原站题解
javascript 解法, 执行用时: 266 ms, 内存消耗: 80.7 MB, 提交时间: 2024-09-25 09:20:05
/**
* @param {string[]} ideas
* @return {number}
*/
var distinctNames = function(ideas) {
const groups = Array.from({ length: 26 }, () => new Set());
for (const s of ideas) {
groups[s.charCodeAt(0) - 'a'.charCodeAt(0)].add(s.slice(1)); // 按照首字母分组
}
let ans = 0;
for (let a = 1; a < 26; a++) { // 枚举所有组对
for (let b = 0; b < a; b++) {
let m = 0; // 交集的大小
for (const s of groups[a]) {
if (groups[b].has(s)) {
m++;
}
}
ans += (groups[a].size - m) * (groups[b].size - m);
}
}
return ans * 2; // 乘 2 放到最后
};
// 按后缀分组
var distinctNames2 = function(ideas) {
const size = Array(26).fill(0); // 集合大小
const intersection = Array.from({ length: 26 }, () => Array(26).fill(0)); // 交集大小
const groups = {}; // 后缀 -> 首字母
for (let s of ideas) {
const b = s.charCodeAt(0) - 'a'.charCodeAt(0);
size[b]++; // 增加集合大小
const suffix = s.slice(1);
const mask = groups[suffix] ?? 0;
groups[suffix] = mask | 1 << b; // 把 b 加到 mask 中
for (let a = 0; a < 26; a++) { // a 是和 s 有着相同后缀的字符串的首字母
if (mask >> a & 1) { // a 在 mask 中
intersection[b][a]++; // 增加交集大小
intersection[a][b]++;
}
}
}
let ans = 0;
for (let a = 1; a < 26; a++) { // 枚举所有组对
for (let b = 0; b < a; b++) {
const m = intersection[a][b];
ans += (size[a] - m) * (size[b] - m);
}
}
return ans * 2; // 乘 2 放到最后
};
rust 解法, 执行用时: 151 ms, 内存消耗: 8.2 MB, 提交时间: 2024-09-25 09:16:59
use std::collections::HashSet;
use std::collections::HashMap;
impl Solution {
pub fn distinct_names(ideas: Vec<String>) -> i64 {
let mut groups = vec![HashSet::new(); 26];
for s in ideas {
groups[(s.as_bytes()[0] - b'a') as usize].insert(s[1..].to_string()); // 按照首字母分组
}
let mut ans = 0i64;
for a in 1..26 { // 枚举所有组对
for b in 0..a {
let m = groups[a].iter().filter(|&s| groups[b].contains(s)).count(); // 交集的大小
ans += (groups[a].len() - m) as i64 * (groups[b].len() - m) as i64;
}
}
ans * 2 // 乘 2 放到最后
}
// 按照后缀分组
pub fn distinct_names2(ideas: Vec<String>) -> i64 {
let mut size = vec![0; 26]; // 集合大小
let mut intersection = vec![vec![0; 26]; 26]; // 交集大小
let mut groups = HashMap::new(); // 后缀 -> 首字母
for s in ideas {
let b = (s.as_bytes()[0] - b'a') as usize;
size[b] += 1; // 增加集合大小
let suffix = &s[1..];
let mask = *groups.get(suffix).unwrap_or(&0);
groups.insert(suffix.to_string(), mask | 1 << b); // 把 b 加到 mask 中
for a in 0..26 { // a 是和 s 有着相同后缀的首字母
if (mask >> a & 1) > 0 { // a 在 mask 中
intersection[b][a] += 1; // 增加交集大小
intersection[a][b] += 1;
}
}
}
let mut ans = 0i64;
for a in 1..26 { // 枚举所有组对
for b in 0..a {
let m = intersection[a][b];
ans += (size[a] - m) as i64 * (size[b] - m) as i64;
}
}
ans * 2 // 乘 2 放到最后
}
}
python3 解法, 执行用时: 588 ms, 内存消耗: 31.2 MB, 提交时间: 2023-06-13 14:40:43
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
python3 解法, 执行用时: 188 ms, 内存消耗: 28.5 MB, 提交时间: 2023-06-13 14:40:24
# 按首字母分组
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
java 解法, 执行用时: 38 ms, 内存消耗: 55.3 MB, 提交时间: 2023-06-13 14:40:04
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;
}
}
golang 解法, 执行用时: 88 ms, 内存消耗: 10.8 MB, 提交时间: 2023-06-13 14:39:46
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
}
golang 解法, 执行用时: 228 ms, 内存消耗: 10.4 MB, 提交时间: 2023-06-13 14:39:36
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
}
golang 解法, 执行用时: 184 ms, 内存消耗: 10.8 MB, 提交时间: 2023-06-13 14:39:10
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
}
cpp 解法, 执行用时: 248 ms, 内存消耗: 77.6 MB, 提交时间: 2023-06-13 14:38:54
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;
}
};
java 解法, 执行用时: 144 ms, 内存消耗: 55 MB, 提交时间: 2023-06-13 14:38:38
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;
}
}
python3 解法, 执行用时: 7728 ms, 内存消耗: 30.9 MB, 提交时间: 2023-06-13 14:38:14
# 去掉首字母分组
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