Chương trình đếm số chuỗi tối đa mà chúng tôi có thể tạo từ danh sách các từ và số lượng chữ cái trong python

Giả sử chúng ta có một danh sách các chuỗi trong đó mỗi chuỗi chứa hai chữ cái "A" s và "B" s. Ta có hai giá trị a và b. Chúng ta phải tìm số lượng chuỗi tối đa có thể được hình thành. Chúng tôi có thể sử dụng nhiều nhất một số "A" và nhiều nhất b một số "B", mà không cần sử dụng lại.

Vì vậy, nếu đầu vào giống như chuỗi =["AAABB", "AABB", "AA", "BB"] a =4 b =2, thì đầu ra sẽ là 2, vì chúng ta có thể lấy chuỗi bằng cách sử dụng 4 "A "s và 2" B "s [" AABB "," AA "].

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

• cặp:=một danh sách mới
• đối với mỗi w trong chuỗi, thực hiện
  • A:=số "A" trong w
  • B:=kích thước của w - A
  • chèn một cặp (A, B) vào cuối các cặp
• ans:=một bản đồ trong đó (a, b) có giá trị 0
• đối với mỗi pait (A, B) theo cặp, hãy thực hiện
  • temp:=một bản đồ mới từ ans
  • đối với mỗi cặp (temp_a, temp_b) và giá trị wc của ans, thực hiện
    • nếu temp_a> =A và temp_b> =B, thì
      • rem:=a pait (temp_a - A, temp_b - B)
      • temp [rem]:=tối đa của temp [rem] (nếu không có rem, 0) và (wc + 1)
    • ans:=temp
• trả về tối đa danh sách tất cả các giá trị của ans

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

Ví dụ

class Solution:
   def solve(self, strings, a, b):
      pairs = []
      for w in strings:
         A = w.count("A")
         B = len(w) - A
         pairs.append((A, B))
      ans = {(a, b): 0}
      for A, B in pairs:
         temp = dict(ans)
         for (temp_a, temp_b), wc in ans.items():
            if temp_a >= A and temp_b >= B:
               rem = (temp_a - A, temp_b - B)
               temp[rem] = max(temp.get(rem, 0), wc + 1)
         ans = temp
      return max(ans.values())

ob = Solution()
strings = ["AAABB", "AABB", "AA", "BB"]
a = 4
b = 2
print(ob.solve(strings, a, b))

Đầu vào

["AAABB", "AABB", "AA", "BB"], 4, 2

Đầu ra

2