Giả sử chúng ta có một danh sách các từ và một chuỗi được gọi là các chữ cái, chúng ta phải tìm kích thước của từ dài nhất có thể được tạo ra bằng cách sắp xếp lại các chữ cái đã cho. Trong các chữ cái có thể có ký tự dấu hoa thị (*) nó có thể khớp với bất kỳ ký tự nào. Và không nhất thiết phải sử dụng tất cả các chữ cái.
Vì vậy, nếu đầu vào giống như từ =["hoàng tử", "gạo", "giá", "giới hạn", "xin chào"] chữ cái ="* r ** ce *", thì đầu ra sẽ là 6, là từ dài nhất chúng ta có thể làm là "hoàng tử", độ dài là 6.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- có:=một bản đồ chứa các chữ cái và tần số của mỗi phần tử bằng chữ cái
- Xác định một hàm hợp lệ (). Điều này sẽ mất s
- need:=một bản đồ chứa các chữ cái và tần số của mỗi phần tử tính bằng s
- extra:=tổng của tất cả các phần tử của (tối đa là 0 và cần [char] - có [char] cho tất cả các char cần)
- trả về true khi thêm <=has ["*"]
- Từ phương thức chính, hãy làm như sau:
- trả về tối đa tất cả các phần tử trong danh sách [kích thước của từ cho tất cả các từ trong các từ khi từ hợp lệ]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
from collections import Counter class Solution: def solve(self, words, letters): has = Counter(letters) def valid(s): need = Counter(s) extra = sum([max(0, need[char] - has[char]) for char in need]) return extra <= has["*"] return max([len(word) for word in words if valid(word)]) ob = Solution() words = ["prince", "rice", "price", "limit", "hello"] letters = "*r**ce*" print(ob.solve(words, letters))
Đầu vào
["prince", "rice", "price", "limit", "hello"], "*r**ce*"
Đầu ra
6