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