มีรายการคำและสตริง letters หาความยาวคำยาวที่สุดที่จัดเรียงจาก letters ได้ มี * แทนตัวอักษรอะไรก็ได้ ไม่ต้องใช้หมด
เช่น words=["prince","rice","price","limit","hello"], letters="*r**ce*" ให้ 6 ("prince")
ขั้นตอนการแก้ปัญหา
has := Counter(letters)นับตัวอักษรและ *- ฟังก์ชัน
valid(s): นับความต้องการของ s, คำนวณextra = sum(max(0, need[c]-has[c])) - ถ้า
extra <= has["*"]ถูกต้อง - คืนค่า max ความยาวคำที่ valid
ตัวอย่างโค้ด
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[ch]-has[ch]) for ch 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))
อินพุต
["prince","rice","price","limit","hello"], "*r**ce*"
เอาต์พุต
6
