给你一个字符串数组 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 <= 50001 <= words[i].length <= 1001 <= k <= 100words 中的所有字符串均由小写英文字母组成。