Giả sử chúng ta có một từ trong từ điển, và chúng ta phải tìm từ có độ dài tối thiểu từ các từ trong từ điển agiven, nó có tất cả các chữ cái từ chuỗi licensePlate. Bây giờ một từ như vậy được cho là hoàn thành chuỗi licensePlate đã cho. Ở đây, chúng tôi sẽ bỏ qua trường hợp cho các chữ cái. Và nó được đảm bảo một câu trả lời tồn tại. Nếu có nhiều hơn một câu trả lời, thì trả về câu trả lời có dấu hiệu đầu tiên trong mảng.
Biển số xe có thể có cùng một chữ cái xảy ra nhiều lần. Vì vậy, khi một LicensePlate của "PP", từ "cọc" không hoàn thành licensePlate, nhưng từ "topper" thì có.
Vì vậy, nếu đầu vào giống như licensePlate ="1s3 PSt", words =["step", "step", "stripe", "stepple"], thì đầu ra sẽ là "step", là từ có độ dài nhỏ nhất chứa các chữ cái là "S", "P", "S", "T".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- bảng chữ cái:="abcdefghijklmnopqrstuvwxyz"
- chữ cái:=danh sách các chữ cái viết thường bằng cách lấy tất cả các chữ cái từ licensePlate khi chữ cái s ở trong bảng chữ cái
- valid_words:=một danh sách mới
- đối với mỗi i trong các từ, hãy thực hiện
- append:=True
- đối với mỗi j trong các chữ cái, hãy thực hiện
- append:=append và (số chữ j trong chữ cái <=số chữ j trong chữ i)
- nếu append là true, thì
- chèn tôi vào cuối valid_words
- trả về từ có độ dài tối thiểu trong valid_words
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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"])) Đầu vào
"1s3 PSt", ["step", "steps", "stripe", "stepple"]
Đầu ra
steps