สมมติว่าเรามีคำในพจนานุกรม และเราต้องหาคำที่มีความยาวต่ำสุดจากคำในพจนานุกรมของ agiven ซึ่งมีตัวอักษรทั้งหมดจาก string licensePlate ตอนนี้มีการกล่าวคำดังกล่าวเพื่อทำให้ใบอนุญาตสตริงที่กำหนดสมบูรณ์ ที่นี่เราจะละเว้นตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ และรับประกันว่าจะมีคำตอบ หากมีมากกว่าหนึ่งคำตอบ ให้ส่งคืนคำตอบที่เกิดขึ้นก่อนในอาร์เรย์
แผ่นป้ายทะเบียนอาจมีอักษรตัวเดียวกันเกิดขึ้นหลายครั้ง ดังนั้นเมื่อใบอนุญาตของ "PP" คำว่า "กอง" ไม่ได้ทำให้ป้ายทะเบียนสมบูรณ์ แต่คำว่า "ท็อปเปอร์" ทำหน้าที่แทน
ดังนั้น หากอินพุตเหมือนกับ licensePlate ="1s3 PSt", words =["step", "steps", "stripe", "stepple"] ผลลัพธ์จะเป็น "steps" เป็นคำที่มีความยาวน้อยที่สุดที่มี ตัวอักษรคือ "S", "P", "S", "T"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตัวอักษร :="abcdefghijklmnopqrstuvwxyz"
- letters :=รายการของ s เป็นตัวพิมพ์เล็กโดยนำ s ทั้งหมดจาก licensePlate เมื่อ s เป็นตัวอักษร
- valid_words :=รายการใหม่
- สำหรับแต่ละ i ในคำพูด ทำ
- ต่อท้าย :=จริง
- สำหรับแต่ละ j ในตัวอักษร ทำ
- ต่อท้าย :=ต่อท้ายและ (จำนวน j ในตัวอักษร <=จำนวน j ใน i)
- ถ้าผนวกเป็นจริง
- ใส่ i ต่อท้าย valid_words
- ส่งคืนคำที่มีความยาวขั้นต่ำใน valid_words
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def shortestCompletingWord(self, licensePlate, words):
alphabet = "abcdefghijklmnopqrstuvwxyz"
letters = [s.lower() for s in licensePlate if s.lower() in alphabet]
valid_words = []
for i in words:
append = True
for j in letters:
append = append and (letters.count(j) <= i.count(j))
if append:
valid_words.append(i)
return min(valid_words, key=len)
ob = Solution()
print(ob.shortestCompletingWord("1s3 PSt", ["step", "steps",
"stripe", "stepple"])) อินพุต
"1s3 PSt", ["step", "steps", "stripe", "stepple"]
ผลลัพธ์
steps
