Shortest Completing Word ใน Python: หาคำสั้นที่สุดครอบคลุมตัวอักษรป้ายทะเบียน

ได้สตริง licensePlate (อาจมีตัวเลข สัญลักษณ์ ตัวพิมพ์ใหญ่/เล็ก) และรายการคำ words ต้องการคำที่สั้นที่สุดใน words ที่มีตัวอักษรครอบคลุมทุกตัวอักษรใน licensePlate (ไม่นับตัวเลข/สัญลักษณ์, ไม่สนใจพิมพ์ใหญ่/เล็ก) หากมีหลายคำ คืนตัวแรกในอาร์เรย์

ตัวอย่าง

licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] → ตัวอักษรที่ต้องการ: s,p,s,t → คำสั้นที่สุดคือ "steps"

ขั้นตอนการแก้ปัญหา

1. ดึงตัวอักษรจาก licensePlate เฉพาะ a-z (แปลงเป็นพิมพ์เล็ก)
2. วนแต่ละคำใน words: ตรวจสอบว่ามีตัวอักษรแต่ละตัวครบตามจำนวนที่ต้องการหรือไม่
3. เก็บคำที่ผ่านเงื่อนไข
4. คืนคำที่สั้นที่สุด (ใช้ min(..., key=len))

การติดตั้งใน Python

class Solution:
    def shortestCompletingWord(self, licensePlate, words):
        import string
        letters = [c.lower() for c in licensePlate if c.lower() in string.ascii_lowercase]
        valid = []
        for w in words:
            if all(letters.count(ch) <= w.count(ch) for ch in set(letters)):
                valid.append(w)
        return min(valid, key=len)

ob = Solution()
print(ob.shortestCompletingWord("1s3 PSt", ["step","steps","stripe","stepple"]))  # steps

อินพุต / เอาต์พุต

Input: "1s3 PSt", ["step","steps","stripe","stepple"]
Output: steps