2026-06-11：前缀连接组的数目。用go语言，给你一个字符串数组 words 和一个整数 k。 如果两个来自不同位置的单词 a、b 满足：它们从开头开始的前 k 个字符完全相同（即 a 的前 k

2026-06-11：前缀连接组的数目。用go语言，给你一个字符串数组 words 和一个整数 k。
如果两个来自不同位置的单词 a、b 满足：它们从开头开始的前 k 个字符完全相同（即 a 的前 k 位等于 b 的前 k 位），那么称这两个单词“可前缀连接”。

一个“连接组”指由一些单词组成的集合，并且集合中的任意两两个单词都两两满足“可前缀连接”。

要求你统计：在给定的 words 中，能形成的、包含至少两个单词的连接组的数量。

注意：长度少于 k 的单词无法提供有效前 k 位前缀，因此必须忽略。即使字符串内容重复，也算作不同的单词。

1 <= words.length <= 5000。

1 <= words[i].length <= 100。

1 <= k <= 100。

words 中的所有字符串均由小写英文字母组成。

输入： words = [“apple”,“apply”,“banana”,“bandit”], k = 2。

输出： 2。

解释：

共享相同前 k = 2 个字母的单词被分为一组：

words[0] = “apple” 和 words[1] = “apply” 共享前缀 “ap”。

words[2] = “banana” 和 words[3] = “bandit” 共享前缀 “ba”。

因此，共有 2 个连接组，每个组至少包含两个单词。

题目来自力扣3839。

前缀连接组数目解题过程

第一步：初始化统计工具

创建一个空的哈希映射（字典），作用是：键 = 有效前缀（前k个字符），值 = 该前缀出现的单词数量。
同时定义一个结果变量，初始值为0，用于记录最终符合条件的连接组数量。

第二步：遍历所有单词，筛选有效单词并统计前缀

逐个处理字符串数组中的每一个单词，执行以下操作：

1. 判断单词是否有效：检查当前单词的长度是否 ≥ k。
   • 如果长度 < k：直接忽略该单词，不做任何处理；
   • 如果长度 ≥ k：该单词为有效单词，继续下一步。
2. 提取有效前缀：截取有效单词的前k个字符作为前缀。
3. 更新统计映射：在哈希映射中，将该前缀对应的计数 +1。

具体执行过程：

1. 处理apple：长度5≥2，提取前缀ap，映射中ap:1；
2. 处理apply：长度5≥2，提取前缀ap，映射中ap:2；
3. 处理banana：长度6≥2，提取前缀ba，映射中ba:1；
4. 处理bandit：长度6≥2，提取前缀ba，映射中ba:2。

最终哈希映射结果：ap:2、ba:2。

第三步：遍历统计映射，计算符合条件的连接组数量

连接组的定义：包含至少两个单词的前缀组。
因此我们遍历哈希映射中的所有计数值：

1. 逐个读取每个前缀对应的出现次数；
2. 如果次数> 1（说明该前缀下有至少两个单词，能形成一个有效连接组）；
3. 每满足一次条件，结果变量就 +1。

具体执行过程：

1. 前缀ap计数=2>1 → 结果+1（结果=1）；
2. 前缀ba计数=2>1 → 结果+1（结果=2）。

第四步：返回最终结果

最终结果为2，与题目示例输出一致。

时间复杂度与额外空间复杂度分析

1. 总时间复杂度

我们分两步计算核心操作的时间：

1. 遍历单词统计前缀：需要遍历n个单词（n是words的长度，最大5000），每个单词截取前k个字符的操作是O(k)，总耗时O(n*k)；
2. 遍历哈希映射统计结果：哈希映射的键数量最多为n（所有前缀都不重复），遍历耗时O(n)。

综合来看，总时间复杂度为 O(n * k)。

• n：字符串数组的长度
• k：指定的前缀长度

2. 总额外空间复杂度

额外空间指除了输入数据外，程序运行时开辟的内存空间：

1. 核心空间是哈希映射：最坏情况下，所有有效单词的前缀都不重复，哈希映射会存储最多n个键值对；
2. 其他变量（计数、结果）都是常数级空间O(1)。

因此，总额外空间复杂度为 O(n)。

总结

1. 解题核心：用哈希表统计有效前缀的出现次数，再统计次数≥2的前缀数量；
2. 时间复杂度：O(n*k)，高效适配题目给定的数据范围；
3. 空间复杂度：O(n)，仅使用哈希表存储前缀统计数据。

Go完整代码如下：

packagemainimport("fmt")funcprefixConnected(words[]string,kint)(ansint){cnt:=map[string]int{}for_,w:=rangewords{iflen(w)>=k{cnt[w[:k]]++}}for_,c:=rangecnt{ifc>1{ans++}}return}funcmain(){words:=[]string{"apple","apply","banana","bandit"}k:=2result:=prefixConnected(words,k)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defprefixConnected(words,k):cnt={}forwinwords:iflen(w)>=k:prefix=w[:k]cnt[prefix]=cnt.get(prefix,0)+1ans=0forcincnt.values():ifc>1:ans+=1returnansif__name__=="__main__":words=["apple","apply","banana","bandit"]k=2result=prefixConnected(words,k)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<string>#include<unordered_map>usingnamespacestd;intprefixConnected(vector<string>&words,intk){unordered_map<string,int>cnt;for(conststring&w:words){if(w.length()>=k){string prefix=w.substr(0,k);cnt[prefix]++;}}intans=0;for(constauto&pair:cnt){if(pair.second>1){ans++;}}returnans;}intmain(){vector<string>words={"apple","apply","banana","bandit"};intk=2;intresult=prefixConnected(words,k);cout<<result<<endl;return0;}