Cho danh sách từ (words) và tập ký tự (characters). Tìm các từ có thể tạo ra chỉ dùng các ký tự trong tập cho phép, mỗi ký tự dùng tối đa số lần xuất hiện.
Ví dụ
words = ["hi", "hello", "bye", "good"] characters = ["h", "i", "b", "y", "e"] Output: hi, bye
"hello" cần 2 'l' và 'o' không có. "good" cần 'g','o','o','d' không đủ.
Thuật toán: Đếm tần suất ký tự (Frequency Count)
- Đếm tần suất ký tự trong tập cho phép → dict/Count.
- Với mỗi từ: đếm tần suất ký tự của từ.
- Kiểm tra: mọi ký tự của từ phải có trong tập cho phép VÀ count_từ <= count_cho_phép.
- Nếu thỏa → in từ.
Mã nguồn
from collections import Counter
words = ["hi", "hello", "bye", "good"]
characters = ["h", "i", "b", "y", "e"]
char_count = Counter(characters)
for word in words:
word_count = Counter(word)
# Kiểm tra mọi ký tự trong từ đều thỏa mãn
if all(word_count[ch] <= char_count.get(ch, 0) for ch in word_count):
print(word)Kết quả
hi bye
Giải thích
Counter(word): {'h':1, 'i':1} cho "hi".all(...): True nếu mọi điều kiện con đều True.char_count.get(ch, 0): trả 0 nếu ký tự không có trong tập cho phép.
Độ phức tạp
- Time: O(W * L) với W số từ, L độ dài trung bình từ.
- Space: O(C + L) cho Counter.
Bài toán liên quan
- Scrabble/Word game: tìm từ điểm cao từ rack chữ cái.
- Anagram solver: từ dùng hết chữ cái cho trước.
- Subset check: set(word).issubset(char_set) - chỉ kiểm tra tồn tại, không kiểm tra số lượng.
Kết luận
collections.Counter là công cụ lý tưởng cho bài toán đếm tần suất và so sánh multiset. Code ngắn, rõ ràng, hiệu quả.