LeetCode 2306 Naming a Company 全解从暴力交换到计数矩阵的四种解法与多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文基于本仓库的 articles/naming-a-company.md 及其配套源码系统讲解 LeetCode 2306「Naming a Company公司命名」的完整解题链路。你将从零开始理解题目中的交换首字母生成新公司名规则掌握暴力枚举、按首字母分组哈希表/数组、增量计数矩阵四种层层递进的做法并学会用集合交集规避无效交换、用 64 位整数规避溢出等关键细节。读完即可在 Python、Java、C、JavaScript、Kotlin 等任意语言中独立写出通过全部测试用例的最优解。题目回顾与前置知识题目给出一组候选单词ideas每个单词由小写字母构成要求从中选出两个不同的单词交换它们的首字母生成两个新名字。只有当两个新名字都不在原始ideas集合中时这一对交换才构成合法的公司名交换后的两个名字是有顺序的第一个名字 第二个名字因此(A, B)与(B, A)是两个不同的公司名。最终需要返回互不相同的合法公司名数量。由于n最大可达 50,000原文档的陷阱章节明确指出该规模答案数量可能远超 32 位整数上限这是后续实现中必须处理的一个关键约束。开始动手前原文档要求你熟悉以下四项基本功Hash Set利用集合的 O(1) 查找快速判断交换后的名字是否已存在于原始列表Hash Map按首字母对单词分组避免对无意义的同首字母交换做无效计算字符串操作提取子串、拼接首字母与剩余后缀集合交集统计两组后缀中的公共元素用于识别交换后仍撞名的无效组合。以下四种解法从最直观的 O(n²) 暴力法逐步优化到线性复杂度的计数矩阵法。每种子方案均保留了原文档的核心代码并可对照仓库中的多语言实现python/2306-naming-a-company.py、java/2306-naming-a-company.java、cpp/2306-naming-a-company.cpp、javascript/2306-naming-a-company.js、kotlin/2306-naming-a-company.kt。解法一暴力枚举Brute Force思路最直接的想法是枚举所有无序对(i, j)交换两者的首字母得到新名字A和B然后检查A、B是否都不在原始集合中。若都不存在就把A B与B A两种顺序都存入一个结果集合最终返回集合大小。该方案正确但很慢需要检查 O(n²) 个配对且每次都要做字符串拼接与集合查询常数开销较大。算法步骤将全部ideas存入集合ideasSet获得 O(1) 查找能力遍历每对(i, j)且i j交换首字母得到两个新名字A、B若A和B都不在ideasSet中则把A B和B A两种顺序加入结果集合res返回res的大小。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: n len(ideas) res set() ideasSet set(ideas) for i in range(n): for j in range(i 1, n): A, B ideas[j][0] ideas[i][1:], ideas[i][0] ideas[j][1:] if A not in ideasSet and B not in ideasSet: res.add(A B) res.add(B A) return len(res)public class Solution { public long distinctNames(String[] ideas) { int n ideas.length; SetString res new HashSet(); SetString ideasSet new HashSet(Arrays.asList(ideas)); for (int i 0; i n; i) { for (int j i 1; j n; j) { String A ideas[j].charAt(0) ideas[i].substring(1); String B ideas[i].charAt(0) ideas[j].substring(1); if (!ideasSet.contains(A) !ideasSet.contains(B)) { res.add(A B); res.add(B A); } } } return res.size(); } }class Solution { public: long long distinctNames(vectorstring ideas) { int n ideas.size(); unordered_setstring res; unordered_setstring ideasSet(ideas.begin(), ideas.end()); for (int i 0; i n; i) { for (int j i 1; j n; j) { string A ideas[j][0] ideas[i].substr(1); string B ideas[i][0] ideas[j].substr(1); if (!ideasSet.count(A) !ideasSet.count(B)) { res.insert(A B); res.insert(B A); } } } return res.size(); } };注意Java 与 C 版本提前使用了long/long long作为返回值类型正是因为答案可能超出 32 位整数范围详见文末陷阱章节。复杂度时间复杂度$O(m \cdot n^2)$空间复杂度$O(m \cdot n^2)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。解法二按首字母分组哈希表思路暴力法的低效根源在于首字母相同的两个单词交换后得到的还是它们本身例如coffee与candy交换首字母后仍是coffee与candy这类配对永远不可能产生新名字。真正有价值的配对只可能发生在首字母不同的两个单词之间。因此可以按首字母将单词分组每组只保留后缀去掉首字符后的部分。对于两个首字母不同的分组交换有效当且仅当某个后缀只出现在其中一个分组若后缀同时出现在两个分组交换后其中一个新名字必然撞上原始单词配对无效记两个分组的交集大小为intersect则「组 A 独有后缀数」|A| - intersect「组 B 独有后缀数」|B| - intersect两组可形成的合法配对数为二者乘积。算法步骤构建映射wordMap键为首字母值为该首字母下的后缀集合遍历每一对不同首字母(char1, char2)统计两个后缀集合的交集大小intersectdistinct1 |group(char1)| - intersectdistinct2 |group(char2)| - intersect累加distinct1 * distinct2到结果返回累加结果。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: wordMap collections.defaultdict(set) for w in ideas: wordMap[w[0]].add(w[1:]) res 0 for char1 in wordMap: for char2 in wordMap: if char1 char2: continue intersect sum(1 for w in wordMap[char1] if w in wordMap[char2]) distinct1 len(wordMap[char1]) - intersect distinct2 len(wordMap[char2]) - intersect res distinct1 * distinct2 return respublic class Solution { public long distinctNames(String[] ideas) { MapCharacter, SetString wordMap new HashMap(); for (String word : ideas) { wordMap.computeIfAbsent( word.charAt(0), k - new HashSet()).add(word.substring(1) ); } long res 0; for (char char1 : wordMap.keySet()) { for (char char2 : wordMap.keySet()) { if (char1 char2) continue; int intersect 0; for (String w : wordMap.get(char1)) { if (wordMap.get(char2).contains(w)) { intersect; } } int distinct1 wordMap.get(char1).size() - intersect; int distinct2 wordMap.get(char2).size() - intersect; res distinct1 * 1L * distinct2; } } return res; } }class Solution { public: long long distinctNames(vectorstring ideas) { unordered_mapchar, unordered_setstring wordMap; for (const string word : ideas) { wordMap[word[0]].insert(word.substr(1)); } long long res 0; for (auto [char1, set1] : wordMap) { for (auto [char2, set2] : wordMap) { if (char1 char2) continue; int intersect 0; for (const string w : set1) { if (set2.count(w)) { intersect; } } int distinct1 set1.size() - intersect; int distinct2 set2.size() - intersect; res distinct1 * 1LL * distinct2; } } return res; } };仓库中的 java/2306-naming-a-company.java 采用的就是该思路map的键是首字母值是该首字母下的后缀HashSet外层对两个键做笛卡尔积内层统计overlap后用(set1.size() - overlap) * (set2.size() - overlap)累加python/2306-naming-a-company.py 则更进一步只枚举prefix_2 prefix_1的无序对直接累加2 * num_suffixes_1 * num_suffixes_2把两种顺序合并进乘法系数同时用len(suffixes) 2提前返回 0。复杂度时间复杂度$O(m \cdot n)$空间复杂度$O(m \cdot n)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。相比暴力法每个后缀只被扫描常数次整体线性。解法三按首字母分组固定数组思路解法二的思想完全正确但哈希表带来了不必要的键散列开销。由于题目保证单词由小写字母构成首字母只有 26 种可能完全可以退化为一固定大小的数组suffixes[i]存储以第i个字母开头的所有后缀通过首字符 - a直接索引省去哈希查找。同时可以进一步优化循环结构只遍历i j的无序对避免每组字母对重复计算两次计算乘积后乘以 2 来同时计入(A, B)与(B, A)两种顺序。算法步骤创建 26 个集合的数组把每个单词的后缀放入首字母索引对应的集合遍历所有(i, j)且i j统计组i与组j的后缀交集intersect计算非重叠后缀数的乘积累加2 × 乘积对应两种排列顺序返回累加结果。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: suffixes [set() for _ in range(26)] for w in ideas: suffixes[ord(w[0]) - ord(a)].add(w[1:]) res 0 for i in range(26): for j in range(i 1, 26): intersect len(suffixes[i] suffixes[j]) res 2 * (len(suffixes[i]) - intersect) * (len(suffixes[j]) - intersect) return respublic class Solution { public long distinctNames(String[] ideas) { SetString[] suffixes new HashSet[26]; for (int i 0; i 26; i) { suffixes[i] new HashSet(); } for (String w : ideas) { suffixes[w.charAt(0) - a].add(w.substring(1)); } long res 0; for (int i 0; i 26; i) { for (int j i 1; j 26; j) { int intersect 0; for (String s : suffixes[i]) { if (suffixes[j].contains(s)) { intersect; } } res 2L * (suffixes[i].size() - intersect) * (suffixes[j].size() - intersect); } } return res; } }class Solution { public: long long distinctNames(vectorstring ideas) { unordered_setstring suffixes[26]; for (const string w : ideas) { suffixes[w[0] - a].insert(w.substr(1)); } long long res 0; for (int i 0; i 26; i) { for (int j i 1; j 26; j) { int intersect 0; for (const string s : suffixes[i]) { if (suffixes[j].count(s)) { intersect; } } res 2LL * (suffixes[i].size() - intersect) * (suffixes[j].size() - intersect); } } return res; } };仓库中的 cpp/2306-naming-a-company.cpp 正是该思路的工程化版本先做dict.size() 2的提前返回不足两个首字母分组时答案必为 0外层用for (char a a; a z; a)与for (char b a 1; b z; b)保证a b只枚举一次随后count 2 * (aKeys * bKeys)javascript/2306-naming-a-company.js 则用same[i][j]二维数组预先把每对分组的交集算好再统一累加(sets[i].size - same[i][j]) * (sets[j].size - same[i][j]) * 2将交集计算与结果累加解耦。kotlin/2306-naming-a-company.kt 给出了使用 Kotlin 标准库intersect()与手写交集计数两种等价写法。复杂度时间复杂度$O(m \cdot n)$空间复杂度$O(m \cdot n)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。循环上限固定为 $\binom{26}{2}$ 对字母组合与数组大小无关。解法四计数矩阵Counting思路解法二、三对每个字母对都要重新计算一次交集存在重复扫描。计数法把逐对求交集转化为按后缀增量维护统计量对每个后缀记录它出现在哪些首字母下一个长度 26 的布尔数组维护 26×26 的计数矩阵count[i][j]表示到目前为止有多少个后缀出现在字母 i 下、但未出现在字母 j 下处理某个后缀时若它出现在字母i下而未出现在字母j下那么之前所有出现在 j、未出现在 i的后缀即count[j][i]与当前后缀恰好构成一组合法配对——因为交换后两个新名字都不撞原始单词。算法步骤构建suffix → 长度为 26 的布尔数组的映射布尔位标记该后缀出现的首字母初始化 26×26 的count矩阵为全零遍历每个后缀及其布尔数组对每个arr[i] True的字母i对每个arr[j] False的字母jcount[i][j] 1res count[j][i]这些是与当前后缀互补的合法配对返回2 * res补上两种排列顺序。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: mp defaultdict(lambda: [False] * 26) count [[0] * 26 for _ in range(26)] res 0 for s in ideas: first_char ord(s[0]) - ord(a) suffix s[1:] mp[suffix][first_char] True for suffix, arr in mp.items(): for i in range(26): if arr[i]: for j in range(26): if not arr[j]: count[i][j] 1 res count[j][i] return 2 * respublic class Solution { public long distinctNames(String[] ideas) { MapString, boolean[] mp new HashMap(); int[][] count new int[26][26]; long res 0; for (String s : ideas) { int firstChar s.charAt(0) - a; String suffix s.substring(1); mp.putIfAbsent(suffix, new boolean[26]); mp.get(suffix)[firstChar] true; } for (boolean[] arr : mp.values()) { for (int i 0; i 26; i) { if (arr[i]) { for (int j 0; j 26; j) { if (!arr[j]) { count[i][j]; res count[j][i]; } } } } } return 2 * res; } }class Solution { public: long long distinctNames(vectorstring ideas) { unordered_mapstring, arraybool, 26 mp; long long count[26][26] {}; long long res 0; for (const string s : ideas) { int firstChar s[0] - a; string suffix s.substr(1); mp[suffix][firstChar] true; } for (auto [suffix, arr] : mp) { for (int i 0; i 26; i) { if (arr[i]) { for (int j 0; j 26; j) { if (!arr[j]) { count[i][j]; res count[j][i]; } } } } } return 2 * res; } };为什么res count[j][i]成立当读到当前后缀出现在i、不出现于j时count[j][i]中累积的每一个旧后缀都满足出现在j、不出现于i。两者交换首字母后旧后缀配上i得到的新名字、当前后缀配上j得到的新名字均不在原始集合中——正好构成一组合法且有方向的配对。由于count[j][i]已隐含方向j为旧后缀的字母、i为新名字的字母最终只需对总量乘以 2 即可补全相反方向。复杂度时间复杂度$O(m \cdot n)$空间复杂度$O(m \cdot n)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。虽然渐近复杂度与解法二、三相同但每个后缀只需处理一次消除了按字母对重复计算交集的开销常数因子更小。四种解法横向对比解法核心思想时间复杂度空间复杂度适用场景暴力枚举枚举所有无序对并交换验证$O(m \cdot n^2)$$O(m \cdot n^2)$仅用于理解题意、验证正确性分组哈希表按首字母分组交集计数$O(m \cdot n)$$O(m \cdot n)$通用解法任意字符集可扩展分组固定数组26 个集合 只枚举i j$O(m \cdot n)$$O(m \cdot n)$题目限定小写字母时首选常数更小计数矩阵后缀 → 布尔数组增量维护count[i][j]$O(m \cdot n)$$O(m \cdot n)$追求最低常数、面试展示进阶思路三种线性解法都能通过全部测试用例区别在于常数因子与代码可读性哈希表版最直观、数组版最适合小写字母约束、计数矩阵版最能体现对计数模型的深层理解。常见陷阱Common Pitfalls原文档在末尾专门列出了五个高频踩坑点逐一说明如下1. 必须同时检查两个交换后的名字合法的公司名要求两个新名字都是全新的。有些实现只检查其中一个是否存在于原始集合却忘了另一个也可能撞名——只要A、B中任意一个已存在于原始ideas该配对即无效。例如ideas [coffee, donuts]这类配对在交换后若产生doffee与conuts二者都不在原始集合中才算合法。2. 区分配对与有序名字题目统计的是有序公司名第一个名字 第二个名字因此找到一组合法交换后(A, B)与(B, A)是两个不同的答案。若忘记乘 2 或只加入一种顺序结果恰好只有正确答案的一半。这也是解法三、四中2 * product与2 * res的来源。3. 同首字母交换不产生新名字两个首字母相同的单词交换后仍是原词永远无效。解法二、三、四都通过只处理不同首字母的分组对天然规避了这一问题如果在实现中不跳过相同首字母的配对不仅浪费计算还可能在交集计数时得到错误结果。4. 后缀提取的边界错误按首字母分组时后缀是去掉首字符后的剩余部分。Python 的s[1:]、Java 的s.substring(1)、C 的s.substr(1)都能正确提取但切片越界、多取或少取一个字符例如误用s[0:]或s[:len-1]会导致集合查询全部失败得到错误答案。仓库源码中 Java 版使用s.substring(1, s.length())、Kotlin 版使用it.substring(1, it.length)显式指定起止可作参考。5. 配对计数的整数溢出当ideas规模达到 50,000 时两个分组大小的乘积每个可达 50,000以及最终答案都会超过 32 位整数上限。Java 中必须使用long源码中res与返回值均为long并在乘法处显式1L *提升精度C 使用long longGo 使用int64Python 的任意精度整数天然无此问题。用int直接累加会在较大数据上溢出并返回错误结果。仓库实现与延伸阅读本仓库针对该题提供了可直接运行的多语言实现全部与本文四种解法一一对应Pythonpython/2306-naming-a-company.py分组数组版含提前返回优化Javajava/2306-naming-a-company.java哈希表分组版Ccpp/2306-naming-a-company.cpp26 字母固定循环版注释标注 O(n) 时空JavaScriptjavascript/2306-naming-a-company.js交集矩阵预计算版Kotlinkotlin/2306-naming-a-company.kt标准库intersect()与手写计数双版本完整题解文档 articles/naming-a-company.md 中还包含 C#、Go、Swift、Rust 等其余语言的逐解法代码可作为跨语言对照学习的材料。若你想温习本解法依赖的基础数据结构仓库中的 implement-prefix-tree.md、top-k-elements-in-list.md、longest-substring-without-duplicates.md 等文章覆盖了集合、哈希与字符串滑动窗口等相邻知识点可以串联阅读。总结本题的核心建模在于首字母决定分组、后缀决定合法性。一旦意识到同首字母交换必然无效、后缀交集即无效配对就能从 O(n²) 暴力法一步跃迁到 O(m·n) 的分组计数法而计数矩阵版本则展示了如何用增量统计彻底消除重复求交集的常数开销。配合 64 位整数与两种顺序 ×2这两个细节即可写出健壮且高效的最终答案。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 2306 Naming a Company 全解：从暴力交换到计数矩阵的四种解法与多语言实现
LeetCode 2306 Naming a Company 全解从暴力交换到计数矩阵的四种解法与多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文基于本仓库的 articles/naming-a-company.md 及其配套源码系统讲解 LeetCode 2306「Naming a Company公司命名」的完整解题链路。你将从零开始理解题目中的交换首字母生成新公司名规则掌握暴力枚举、按首字母分组哈希表/数组、增量计数矩阵四种层层递进的做法并学会用集合交集规避无效交换、用 64 位整数规避溢出等关键细节。读完即可在 Python、Java、C、JavaScript、Kotlin 等任意语言中独立写出通过全部测试用例的最优解。题目回顾与前置知识题目给出一组候选单词ideas每个单词由小写字母构成要求从中选出两个不同的单词交换它们的首字母生成两个新名字。只有当两个新名字都不在原始ideas集合中时这一对交换才构成合法的公司名交换后的两个名字是有顺序的第一个名字 第二个名字因此(A, B)与(B, A)是两个不同的公司名。最终需要返回互不相同的合法公司名数量。由于n最大可达 50,000原文档的陷阱章节明确指出该规模答案数量可能远超 32 位整数上限这是后续实现中必须处理的一个关键约束。开始动手前原文档要求你熟悉以下四项基本功Hash Set利用集合的 O(1) 查找快速判断交换后的名字是否已存在于原始列表Hash Map按首字母对单词分组避免对无意义的同首字母交换做无效计算字符串操作提取子串、拼接首字母与剩余后缀集合交集统计两组后缀中的公共元素用于识别交换后仍撞名的无效组合。以下四种解法从最直观的 O(n²) 暴力法逐步优化到线性复杂度的计数矩阵法。每种子方案均保留了原文档的核心代码并可对照仓库中的多语言实现python/2306-naming-a-company.py、java/2306-naming-a-company.java、cpp/2306-naming-a-company.cpp、javascript/2306-naming-a-company.js、kotlin/2306-naming-a-company.kt。解法一暴力枚举Brute Force思路最直接的想法是枚举所有无序对(i, j)交换两者的首字母得到新名字A和B然后检查A、B是否都不在原始集合中。若都不存在就把A B与B A两种顺序都存入一个结果集合最终返回集合大小。该方案正确但很慢需要检查 O(n²) 个配对且每次都要做字符串拼接与集合查询常数开销较大。算法步骤将全部ideas存入集合ideasSet获得 O(1) 查找能力遍历每对(i, j)且i j交换首字母得到两个新名字A、B若A和B都不在ideasSet中则把A B和B A两种顺序加入结果集合res返回res的大小。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: n len(ideas) res set() ideasSet set(ideas) for i in range(n): for j in range(i 1, n): A, B ideas[j][0] ideas[i][1:], ideas[i][0] ideas[j][1:] if A not in ideasSet and B not in ideasSet: res.add(A B) res.add(B A) return len(res)public class Solution { public long distinctNames(String[] ideas) { int n ideas.length; SetString res new HashSet(); SetString ideasSet new HashSet(Arrays.asList(ideas)); for (int i 0; i n; i) { for (int j i 1; j n; j) { String A ideas[j].charAt(0) ideas[i].substring(1); String B ideas[i].charAt(0) ideas[j].substring(1); if (!ideasSet.contains(A) !ideasSet.contains(B)) { res.add(A B); res.add(B A); } } } return res.size(); } }class Solution { public: long long distinctNames(vectorstring ideas) { int n ideas.size(); unordered_setstring res; unordered_setstring ideasSet(ideas.begin(), ideas.end()); for (int i 0; i n; i) { for (int j i 1; j n; j) { string A ideas[j][0] ideas[i].substr(1); string B ideas[i][0] ideas[j].substr(1); if (!ideasSet.count(A) !ideasSet.count(B)) { res.insert(A B); res.insert(B A); } } } return res.size(); } };注意Java 与 C 版本提前使用了long/long long作为返回值类型正是因为答案可能超出 32 位整数范围详见文末陷阱章节。复杂度时间复杂度$O(m \cdot n^2)$空间复杂度$O(m \cdot n^2)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。解法二按首字母分组哈希表思路暴力法的低效根源在于首字母相同的两个单词交换后得到的还是它们本身例如coffee与candy交换首字母后仍是coffee与candy这类配对永远不可能产生新名字。真正有价值的配对只可能发生在首字母不同的两个单词之间。因此可以按首字母将单词分组每组只保留后缀去掉首字符后的部分。对于两个首字母不同的分组交换有效当且仅当某个后缀只出现在其中一个分组若后缀同时出现在两个分组交换后其中一个新名字必然撞上原始单词配对无效记两个分组的交集大小为intersect则「组 A 独有后缀数」|A| - intersect「组 B 独有后缀数」|B| - intersect两组可形成的合法配对数为二者乘积。算法步骤构建映射wordMap键为首字母值为该首字母下的后缀集合遍历每一对不同首字母(char1, char2)统计两个后缀集合的交集大小intersectdistinct1 |group(char1)| - intersectdistinct2 |group(char2)| - intersect累加distinct1 * distinct2到结果返回累加结果。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: wordMap collections.defaultdict(set) for w in ideas: wordMap[w[0]].add(w[1:]) res 0 for char1 in wordMap: for char2 in wordMap: if char1 char2: continue intersect sum(1 for w in wordMap[char1] if w in wordMap[char2]) distinct1 len(wordMap[char1]) - intersect distinct2 len(wordMap[char2]) - intersect res distinct1 * distinct2 return respublic class Solution { public long distinctNames(String[] ideas) { MapCharacter, SetString wordMap new HashMap(); for (String word : ideas) { wordMap.computeIfAbsent( word.charAt(0), k - new HashSet()).add(word.substring(1) ); } long res 0; for (char char1 : wordMap.keySet()) { for (char char2 : wordMap.keySet()) { if (char1 char2) continue; int intersect 0; for (String w : wordMap.get(char1)) { if (wordMap.get(char2).contains(w)) { intersect; } } int distinct1 wordMap.get(char1).size() - intersect; int distinct2 wordMap.get(char2).size() - intersect; res distinct1 * 1L * distinct2; } } return res; } }class Solution { public: long long distinctNames(vectorstring ideas) { unordered_mapchar, unordered_setstring wordMap; for (const string word : ideas) { wordMap[word[0]].insert(word.substr(1)); } long long res 0; for (auto [char1, set1] : wordMap) { for (auto [char2, set2] : wordMap) { if (char1 char2) continue; int intersect 0; for (const string w : set1) { if (set2.count(w)) { intersect; } } int distinct1 set1.size() - intersect; int distinct2 set2.size() - intersect; res distinct1 * 1LL * distinct2; } } return res; } };仓库中的 java/2306-naming-a-company.java 采用的就是该思路map的键是首字母值是该首字母下的后缀HashSet外层对两个键做笛卡尔积内层统计overlap后用(set1.size() - overlap) * (set2.size() - overlap)累加python/2306-naming-a-company.py 则更进一步只枚举prefix_2 prefix_1的无序对直接累加2 * num_suffixes_1 * num_suffixes_2把两种顺序合并进乘法系数同时用len(suffixes) 2提前返回 0。复杂度时间复杂度$O(m \cdot n)$空间复杂度$O(m \cdot n)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。相比暴力法每个后缀只被扫描常数次整体线性。解法三按首字母分组固定数组思路解法二的思想完全正确但哈希表带来了不必要的键散列开销。由于题目保证单词由小写字母构成首字母只有 26 种可能完全可以退化为一固定大小的数组suffixes[i]存储以第i个字母开头的所有后缀通过首字符 - a直接索引省去哈希查找。同时可以进一步优化循环结构只遍历i j的无序对避免每组字母对重复计算两次计算乘积后乘以 2 来同时计入(A, B)与(B, A)两种顺序。算法步骤创建 26 个集合的数组把每个单词的后缀放入首字母索引对应的集合遍历所有(i, j)且i j统计组i与组j的后缀交集intersect计算非重叠后缀数的乘积累加2 × 乘积对应两种排列顺序返回累加结果。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: suffixes [set() for _ in range(26)] for w in ideas: suffixes[ord(w[0]) - ord(a)].add(w[1:]) res 0 for i in range(26): for j in range(i 1, 26): intersect len(suffixes[i] suffixes[j]) res 2 * (len(suffixes[i]) - intersect) * (len(suffixes[j]) - intersect) return respublic class Solution { public long distinctNames(String[] ideas) { SetString[] suffixes new HashSet[26]; for (int i 0; i 26; i) { suffixes[i] new HashSet(); } for (String w : ideas) { suffixes[w.charAt(0) - a].add(w.substring(1)); } long res 0; for (int i 0; i 26; i) { for (int j i 1; j 26; j) { int intersect 0; for (String s : suffixes[i]) { if (suffixes[j].contains(s)) { intersect; } } res 2L * (suffixes[i].size() - intersect) * (suffixes[j].size() - intersect); } } return res; } }class Solution { public: long long distinctNames(vectorstring ideas) { unordered_setstring suffixes[26]; for (const string w : ideas) { suffixes[w[0] - a].insert(w.substr(1)); } long long res 0; for (int i 0; i 26; i) { for (int j i 1; j 26; j) { int intersect 0; for (const string s : suffixes[i]) { if (suffixes[j].count(s)) { intersect; } } res 2LL * (suffixes[i].size() - intersect) * (suffixes[j].size() - intersect); } } return res; } };仓库中的 cpp/2306-naming-a-company.cpp 正是该思路的工程化版本先做dict.size() 2的提前返回不足两个首字母分组时答案必为 0外层用for (char a a; a z; a)与for (char b a 1; b z; b)保证a b只枚举一次随后count 2 * (aKeys * bKeys)javascript/2306-naming-a-company.js 则用same[i][j]二维数组预先把每对分组的交集算好再统一累加(sets[i].size - same[i][j]) * (sets[j].size - same[i][j]) * 2将交集计算与结果累加解耦。kotlin/2306-naming-a-company.kt 给出了使用 Kotlin 标准库intersect()与手写交集计数两种等价写法。复杂度时间复杂度$O(m \cdot n)$空间复杂度$O(m \cdot n)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。循环上限固定为 $\binom{26}{2}$ 对字母组合与数组大小无关。解法四计数矩阵Counting思路解法二、三对每个字母对都要重新计算一次交集存在重复扫描。计数法把逐对求交集转化为按后缀增量维护统计量对每个后缀记录它出现在哪些首字母下一个长度 26 的布尔数组维护 26×26 的计数矩阵count[i][j]表示到目前为止有多少个后缀出现在字母 i 下、但未出现在字母 j 下处理某个后缀时若它出现在字母i下而未出现在字母j下那么之前所有出现在 j、未出现在 i的后缀即count[j][i]与当前后缀恰好构成一组合法配对——因为交换后两个新名字都不撞原始单词。算法步骤构建suffix → 长度为 26 的布尔数组的映射布尔位标记该后缀出现的首字母初始化 26×26 的count矩阵为全零遍历每个后缀及其布尔数组对每个arr[i] True的字母i对每个arr[j] False的字母jcount[i][j] 1res count[j][i]这些是与当前后缀互补的合法配对返回2 * res补上两种排列顺序。代码实现class Solution: def distinctNames(self, ideas: List[str]) - int: mp defaultdict(lambda: [False] * 26) count [[0] * 26 for _ in range(26)] res 0 for s in ideas: first_char ord(s[0]) - ord(a) suffix s[1:] mp[suffix][first_char] True for suffix, arr in mp.items(): for i in range(26): if arr[i]: for j in range(26): if not arr[j]: count[i][j] 1 res count[j][i] return 2 * respublic class Solution { public long distinctNames(String[] ideas) { MapString, boolean[] mp new HashMap(); int[][] count new int[26][26]; long res 0; for (String s : ideas) { int firstChar s.charAt(0) - a; String suffix s.substring(1); mp.putIfAbsent(suffix, new boolean[26]); mp.get(suffix)[firstChar] true; } for (boolean[] arr : mp.values()) { for (int i 0; i 26; i) { if (arr[i]) { for (int j 0; j 26; j) { if (!arr[j]) { count[i][j]; res count[j][i]; } } } } } return 2 * res; } }class Solution { public: long long distinctNames(vectorstring ideas) { unordered_mapstring, arraybool, 26 mp; long long count[26][26] {}; long long res 0; for (const string s : ideas) { int firstChar s[0] - a; string suffix s.substr(1); mp[suffix][firstChar] true; } for (auto [suffix, arr] : mp) { for (int i 0; i 26; i) { if (arr[i]) { for (int j 0; j 26; j) { if (!arr[j]) { count[i][j]; res count[j][i]; } } } } } return 2 * res; } };为什么res count[j][i]成立当读到当前后缀出现在i、不出现于j时count[j][i]中累积的每一个旧后缀都满足出现在j、不出现于i。两者交换首字母后旧后缀配上i得到的新名字、当前后缀配上j得到的新名字均不在原始集合中——正好构成一组合法且有方向的配对。由于count[j][i]已隐含方向j为旧后缀的字母、i为新名字的字母最终只需对总量乘以 2 即可补全相反方向。复杂度时间复杂度$O(m \cdot n)$空间复杂度$O(m \cdot n)$其中 $n$ 是ideas数组的大小$m$ 是字符串的平均长度。虽然渐近复杂度与解法二、三相同但每个后缀只需处理一次消除了按字母对重复计算交集的开销常数因子更小。四种解法横向对比解法核心思想时间复杂度空间复杂度适用场景暴力枚举枚举所有无序对并交换验证$O(m \cdot n^2)$$O(m \cdot n^2)$仅用于理解题意、验证正确性分组哈希表按首字母分组交集计数$O(m \cdot n)$$O(m \cdot n)$通用解法任意字符集可扩展分组固定数组26 个集合 只枚举i j$O(m \cdot n)$$O(m \cdot n)$题目限定小写字母时首选常数更小计数矩阵后缀 → 布尔数组增量维护count[i][j]$O(m \cdot n)$$O(m \cdot n)$追求最低常数、面试展示进阶思路三种线性解法都能通过全部测试用例区别在于常数因子与代码可读性哈希表版最直观、数组版最适合小写字母约束、计数矩阵版最能体现对计数模型的深层理解。常见陷阱Common Pitfalls原文档在末尾专门列出了五个高频踩坑点逐一说明如下1. 必须同时检查两个交换后的名字合法的公司名要求两个新名字都是全新的。有些实现只检查其中一个是否存在于原始集合却忘了另一个也可能撞名——只要A、B中任意一个已存在于原始ideas该配对即无效。例如ideas [coffee, donuts]这类配对在交换后若产生doffee与conuts二者都不在原始集合中才算合法。2. 区分配对与有序名字题目统计的是有序公司名第一个名字 第二个名字因此找到一组合法交换后(A, B)与(B, A)是两个不同的答案。若忘记乘 2 或只加入一种顺序结果恰好只有正确答案的一半。这也是解法三、四中2 * product与2 * res的来源。3. 同首字母交换不产生新名字两个首字母相同的单词交换后仍是原词永远无效。解法二、三、四都通过只处理不同首字母的分组对天然规避了这一问题如果在实现中不跳过相同首字母的配对不仅浪费计算还可能在交集计数时得到错误结果。4. 后缀提取的边界错误按首字母分组时后缀是去掉首字符后的剩余部分。Python 的s[1:]、Java 的s.substring(1)、C 的s.substr(1)都能正确提取但切片越界、多取或少取一个字符例如误用s[0:]或s[:len-1]会导致集合查询全部失败得到错误答案。仓库源码中 Java 版使用s.substring(1, s.length())、Kotlin 版使用it.substring(1, it.length)显式指定起止可作参考。5. 配对计数的整数溢出当ideas规模达到 50,000 时两个分组大小的乘积每个可达 50,000以及最终答案都会超过 32 位整数上限。Java 中必须使用long源码中res与返回值均为long并在乘法处显式1L *提升精度C 使用long longGo 使用int64Python 的任意精度整数天然无此问题。用int直接累加会在较大数据上溢出并返回错误结果。仓库实现与延伸阅读本仓库针对该题提供了可直接运行的多语言实现全部与本文四种解法一一对应Pythonpython/2306-naming-a-company.py分组数组版含提前返回优化Javajava/2306-naming-a-company.java哈希表分组版Ccpp/2306-naming-a-company.cpp26 字母固定循环版注释标注 O(n) 时空JavaScriptjavascript/2306-naming-a-company.js交集矩阵预计算版Kotlinkotlin/2306-naming-a-company.kt标准库intersect()与手写计数双版本完整题解文档 articles/naming-a-company.md 中还包含 C#、Go、Swift、Rust 等其余语言的逐解法代码可作为跨语言对照学习的材料。若你想温习本解法依赖的基础数据结构仓库中的 implement-prefix-tree.md、top-k-elements-in-list.md、longest-substring-without-duplicates.md 等文章覆盖了集合、哈希与字符串滑动窗口等相邻知识点可以串联阅读。总结本题的核心建模在于首字母决定分组、后缀决定合法性。一旦意识到同首字母交换必然无效、后缀交集即无效配对就能从 O(n²) 暴力法一步跃迁到 O(m·n) 的分组计数法而计数矩阵版本则展示了如何用增量统计彻底消除重复求交集的常数开销。配合 64 位整数与两种顺序 ×2这两个细节即可写出健壮且高效的最终答案。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考