Chương trình tìm độ dài từ dài nhất có thể tạo từ các chữ cái cho trước bằng Python

Cho danh sách words và chuỗi letters (có thể chứa '*' khớp bất kỳ ký tự). Tìm độ dài từ dài nhất trong words có thể tạo được từ letters (không bắt buộc dùng hết).

Ví dụ: words=["prince","rice","price","limit","hello"], letters="*r**ce*" → 6 ("prince").

Giải thuật

• Đếm tần suất ký tự trong letters (has).
• Hàm valid(s): đếm tần suất trong s (need), tính extra = sum(max(0, need[c]-has[c])). Hợp lệ nếu extra <= has['*'].
• Lọc từ hợp lệ, lấy max độ dài.

Ví dụ minh họa

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