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

Cho danh sách chuỗi words và chuỗi letters. Tìm độ dài chuỗi dài nhất trong words có thể tạo từ các ký tự trong letters. Không được dùng lại ký tự. Nếu không có từ nào, trả về 0.

Ví dụ, words = ["dog", "cat", "rat", "bunny", "lion", "bat"], letters = "gabctnyu", đầu ra là 3, vì có thể tạo "cat" hoặc "bat", độ dài tối đa 3.

Các bước giải quyết:

• ref := bản đồ tần suất ký tự của letters.
• max_len := 0.
• Duyệt từng word trong words:
  • w := bản đồ tần suất ký tự của word.
  • l := len(word).
  • counter := 0.
  • Duyệt từng ký tự k trong w:
    • Nếu w[k] <= ref[k], tăng counter.
    • Ngược lại, thoát vòng lặp.
  • Nếu l > max_len và len(w) == counter, cập nhật max_len = l.
• Trả về max_len.

Ví dụ minh họa

from collections import Counter

class Solution:
    def solve(self, words, letters):
        ref = Counter(letters)
        max_len = 0
        for word in words:
            w = Counter(word)
            l = len(word)
            counter = 0
            for k in w:
                if w[k] <= ref[k]:
                    counter += 1
                else:
                    break
            if l > max_len and len(w) == counter:
                max_len = l
        return max_len

ob = Solution()
words = ["dog", "cat", "rat", "bunny", "lion", "bat"]
letters = "gabctnyu"
print(ob.solve(words, letters))

Đầu vào

["dog", "cat", "rat", "bunny", "lion", "bat"], "gabctnyu"

Đầu ra

3