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

福大大架构师每日一题

发布于 2026-06-12 18:08:44

350

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完整代码如下：

package main

import (
    "fmt"
)

func prefixConnected(words []string, k int) (ans int) {
    cnt := map[string]int{}
    for _, w := range words {
        iflen(w) >= k {
            cnt[w[:k]]++
        }
    }

    for _, c := range cnt {
        if c > 1 {
            ans++
        }
    }
    return
}

func main() {
    words := []string{"apple", "apply", "banana", "bandit"}
    k := 2
    result := prefixConnected(words, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def prefixConnected(words, k):
    cnt = {}
    for w in words:
        iflen(w) >= k:
            prefix = w[:k]
            cnt[prefix] = cnt.get(prefix, 0) + 1

    ans = 0
    for c in cnt.values():
        if c > 1:
            ans += 1
    return ans

if __name__ == "__main__":
    words = ["apple", "apply", "banana", "bandit"]
    k = 2
    result = prefixConnected(words, k)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

int prefixConnected(vector<string>& words, int k) {
    unordered_map<string, int> cnt;

    for (conststring& w : words) {
        if (w.length() >= k) {
            string prefix = w.substr(0, k);
            cnt[prefix]++;
        }
    }

    int ans = 0;
    for (const auto& pair : cnt) {
        if (pair.second > 1) {
            ans++;
        }
    }

    return ans;
}

int main() {
    vector<string> words = {"apple", "apply", "banana", "bandit"};
    int k = 2;
    int result = prefixConnected(words, k);
    cout << result << endl;

    return0;
}