目录

一、题目

1、题目描述

2、接口描述

python3

cpp

C#

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

python3

cpp

C#

---

一、题目

1、题目描述

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

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

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

2、接口描述

python3

 ​

    def distinctNames(self, ideas: List[str]) -> int:

cpp

 ​

class Solution {
public:long long distinctNames(vector<string>& ideas) {}
};

C#

 ​

public class Solution
{public long DistinctNames(string[] ideas){}
}

3、原题链接

2306. 公司命名

---

二、解题报告

1、思路分析

考虑每个首字符出现次数 cnt[]

答案是 cnt[i] * cnt[j] 其中 j < i 吗？

会有非法的

非法的满足什么？

对于不同的i, j，却有着相同的 s[1::]

我们可以将字符串按照后缀分组，遍历字符串数组，计算每个后缀的重叠 pair(i, j) 数目即可

2、复杂度

时间复杂度： O(n(m + U))空间复杂度：O(U^2 + nm)

3、代码详解

python3

 ​

class Solution:def distinctNames(self, ideas: list[str]) -> int:cnt = [0] * 26g = [[0] * 26 for _ in range(26)]adj = defaultdict(list)for s in ideas:a = ord(s[0]) - ord('a')st = adj[s[1::]]for b in st:g[a][b] += 1g[b][a] += 1st.append(a)cnt[a] += 1res = 0for a in range(1, 26):for b in range(a):m = g[a][b]res += (cnt[a] - m) * (cnt[b] - m)return res * 2

cpp

 ​

class Solution {
public:long long distinctNames(vector<string>& ideas) {std::unordered_map<std::string, std::vector<int>> mp;std::array<int, 26> cnt{};std::vector<std::array<int, 26>> g(26, std::array<int, 26>{});for (auto &s : ideas) {auto &st = mp[s.substr(1)];int a = s[0] - 'a';for (int b : st)++ g[a][b], ++ g[b][a];st.push_back(a);++ cnt[a];}long long res = 0;for (int a = 1; a < 26; ++ a)for (int b = 0; b < a; ++ b) {int m = g[a][b];res += 1LL * (cnt[a] - m) * (cnt[b] - m);}return res * 2;}
};

C#

 ​

public class Solution
{public long DistinctNames(string[] ideas){IDictionary<string, List<int>> mp = new Dictionary<string, List<int>>();int[] cnt = new int[26];int[,] g = new int[26, 26];foreach (string s in ideas){var sb = s.Substring(1);if (!mp.ContainsKey(sb))mp.Add(sb, new List<int>());List<int> st = mp[sb];int a = s[0] - 'a';foreach(int b in st){++g[a, b];++g[b, a];}++cnt[a];st.Add(a);}long res = 0;for(int a = 1; a < 26; ++ a)for(int b = 0; b < a; ++ b){int m = g[a, b];res += 1L * (cnt[a] - m) * (cnt[b] - m);}return res * 2;}
}