Medium

题目描述

给定一个字符串数组 words 和一个整数 k。

如果两个位于不同索引的单词 a 和 b 满足 a[0..k-1] == b[0..k-1]，则它们是前缀连接的。

连接组是一个单词集合，其中每对单词都是前缀连接的。

返回由给定单词形成的包含至少两个单词的连接组数量。

注意：

  • 长度小于 k 的单词无法加入任何组，将被忽略。
  • 重复的字符串被视为单独的单词。

示例 1：

输入：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 个连接组，每个组都包含至少两个单词。

示例 2：

输入：words = ["car","cat","cartoon"], k = 3
输出：1
解释：
对长度为 k = 3 的前缀进行评估：
- words[0] = "car" 和 words[2] = "cartoon" 共享前缀 "car"。
- words[1] = "cat" 不与任何其他单词共享长度为 3 的前缀。
因此，有 1 个连接组。

示例 3：

输入：words = ["bat","dog","dog","doggy","bat"], k = 3
输出：2
解释：
对长度为 k = 3 的前缀进行评估：
- words[0] = "bat" 和 words[4] = "bat" 形成一个组。
- words[1] = "dog"、words[2] = "dog" 和 words[3] = "doggy" 共享前缀 "dog"。
因此，有 2 个连接组，每个组都包含至少两个单词。

约束条件：

  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 100
  • 1 <= k <= 100
  • words 中的所有字符串都由小写英文字母组成。

解题思路

解题思路

这道题本质上是一个分组问题，需要根据字符串的前k个字符将单词进行分类。

核心思想：

  1. 首先过滤掉长度小于k的单词，因为它们无法参与任何有效组
  2. 对于剩余的单词，提取每个单词的前k个字符作为前缀
  3. 使用哈希表统计每个前缀对应的单词数量
  4. 最后统计有多少个前缀对应的单词数量≥2

算法步骤：

  1. 遍历words数组，对于每个长度≥k的单词
  2. 提取其前k个字符作为key
  3. 在哈希表中记录该前缀对应的单词计数
  4. 遍历哈希表，统计值≥2的键的数量

这种方法的优势是简单直接，时间复杂度线性，空间复杂度也很优秀。由于前缀长度固定为k，字符串操作的时间复杂度是常数级别的。

推荐解法： 哈希表计数法，实现简单且效率高。

代码实现

class Solution {
public:
    int prefixConnected(vector<string>& words, int k) {
        unordered_map<string, int> prefixCount;
        
        for (const string& word : words) {
            if (word.length() >= k) {
                string prefix = word.substr(0, k);
                prefixCount[prefix]++;
            }
        }
        
        int result = 0;
        for (const auto& pair : prefixCount) {
            if (pair.second >= 2) {
                result++;
            }
        }
        
        return result;
    }
};

class Solution:
    def prefixConnected(self, words: List[str], k: int) -> int:
        prefix_count = {}
        
        for word in words:
            if len(word) >= k:
                prefix = word[:k]
                prefix_count[prefix] = prefix_count.get(prefix, 0) + 1
        
        result = 0
        for count in prefix_count.values():
            if count >= 2:
                result += 1
        
        return result

public class Solution {
    public int PrefixConnected(string[] words, int k) {
        Dictionary<string, int> prefixCount = new Dictionary<string, int>();
        
        foreach (string word in words) {
            if (word.Length >= k) {
                string prefix = word.Substring(0, k);
                if (prefixCount.ContainsKey(prefix)) {
                    prefixCount[prefix]++;
                } else {
                    prefixCount[prefix] = 1;
                }
            }
        }
        
        int result = 0;
        foreach (int count in prefixCount.Values) {
            if (count >= 2) {
                result++;
            }
        }
        
        return result;
    }
}

var prefixConnected = function(words, k) {
    const prefixCount = new Map();
    
    for (const word of words) {
        if (word.length >= k) {
            const prefix = word.substring(0, k);
            prefixCount.set(prefix, (prefixCount.get(prefix) || 0) + 1);
        }
    }
    
    let result = 0;
    for (const count of prefixCount.values()) {
        if (count >= 2) {
            result++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × k)，其中n是words数组长度，k是前缀长度。需要遍历所有单词并提取前缀
空间复杂度O(m × k)，其中m是不同前缀的数量，最坏情况下m = n。每个前缀字符串占用O(k)空间