Chương trình tìm số lượng danh sách con chứa chính xác k từ khác nhau trong Python

Giả sử chúng ta có một danh sách các từ và một giá trị khác k. Chúng ta phải tìm số lượng danh sách con trong các từ đã cho sao cho có đúng k từ khác nhau.

Vì vậy, nếu đầu vào giống như words =["Kolkata", "Delhi", "Delhi", "Kolkata"] k =2, thì đầu ra sẽ là 5, vì danh sách con sau có 2 từ duy nhất:["Kolkata" , "Delhi"], ["Delhi", "Kolkata"], ["Kolkata", "Delhi", "Delhi"], ["Delhi", "Delhi", "Kolkata"], ["Kolkata", " Delhi "," Delhi "," Kolkata "], nhưng không phải [" Delhi "," Delhi "] vì chỉ có một từ duy nhất.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm work (). Điều này sẽ cần lời nói, k
n:=kích thước của từ
nếu k giống 0, thì
- trả về 0
cnt:=một bản đồ mới
ans:=0
l:=0
đối với r trong phạm vi từ 0 đến n, thực hiện
- từ:=words [r]
- nếu từ không có trong cnt, thì
  - cnt [word]:=0
- cnt [word]:=cnt [word] + 1
- while kích thước của cnt> k, do
  - cnt [words [l]]:=cnt [words [l]] - 1
  - nếu cnt [words [l]] giống 0, thì
    - xoá các từ [l] khỏi cnt
  - l:=l + 1
- ans:=ans + r - l + 1
trả lại ans

Từ phương thức chính trả về (công việc (từ, k) - công việc (từ, k - 1))

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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