在Python中查找包含确切k个不同单词的子列表的程序

假设我们有一个单词列表和另一个值k。我们必须找到给定单词中恰好包含k个不同单词的子列表的数量。

因此，如果输入如下words = [“Kolkata”, “Delhi”, “Delhi”, “Kolkata”] k = 2，那么输出将为5，因为以下子列表具有2个唯一单词：[“Kolkata”，“Delhi”]，[“Delhi”，“Kolkata”]，[“Kolkata”，“Delhi”，“Delhi”]，[“Delhi”，“Delhi”，“Kolkata”]，[“ Kolkata”，“Delhi”，“Delhi”，“Kolkata”]，但不是[“ Delhi”，“Delhi”]，因为只有一个唯一的单词。

要解决这个问题，我们将遵循以下步骤−

• 定义一个函数work()。这将取words，k
• n := words的大小
• 如果k与0相同，则
  • 返回0
• cnt: =一个新映射
• ans：= 0
• l：= 0
• 对于r在0到n的范围内，执行以下操作
  • word：= words[r]
  • 如果cnt中不存在word，则
    • cnt[word]：= 0
  • cnt[word]：= cnt[word] + 1
  • 当cnt的大小> k时，执行以下操作
    • cnt[words[l]]：= cnt[words[l]] – 1
    • 如果cnt[words[l]]与0相同，则
    • 从cnt中删除words[l]
    • l：= l + 1
  • ans：= ans + r – l + 1
• 返回ans

从main方法返回(work(words, k) – work(words, k – 1))

更多Python相关文章，请阅读：Python 教程

示例（Python）

让我们查看以下实现以获得更好的理解−

class Solution:
   def solve(self, words, k):
      return self.work(words, k) - self.work(words, k - 1)
   def work(self, words, k):
      n = len(words)
      if k == 0:
         return 0
      cnt = dict()
      ans = 0
      l = 0
      for r in range(n):
         word = words[r]
         if word not in cnt:
            cnt[word] = 0
         cnt[word] += 1
         while len(cnt) > k:
            cnt[words[l]] -= 1
            if cnt[words[l]] == 0:
               del cnt[words[l]]
            l += 1
         ans += r - l + 1
      return ans
ob = Solution()
words = ["Kolkata", "Delhi", "Delhi", "Kolkata"]
k = 2
print(ob.solve(words, k))

输入

["Kolkata", "Delhi", "Delhi", "Kolkata"]，2

输入

5