Giả sử ta có một từ điển words, và ta cần tìm từ có độ dài nhỏ nhất từ từ điển đã cho, nó chứa tất cả các chữ cái từ chuỗi licensePlate. Từ như vậy được gọi là hoàn thành chuỗi licensePlate cho trước. Ở đây, ta sẽ bỏ qua chữ hoa/thường cho các chữ cái. Và đảm bảo luôn có đáp án. Nếu có nhiều đáp án, trả về đáp án xuất hiện đầu tiên trong mảng.
Trong biển số xe có thể có cùng một chữ cái xuất hiện nhiều lần. Ví dụ, với licensePlate "PP", từ "pile" không hoàn thành licensePlate, nhưng từ "topper" thì hoàn thành.
Ví dụ, nếu đầu vào là licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"], thì đầu ra sẽ là "steps", vì từ có độ dài nhỏ nhất chứa các chữ cái là "S", "P", "S", "T".
Để giải quyết, ta thực hiện các bước sau:
- alphabet := "abcdefghijklmnopqrstuvwxyz"
- letters := danh sách các s viết thường bằng cách lấy tất cả s từ licensePlate khi s nằm trong alphabet
- valid_words := một danh sách mới
- Với mỗi i trong words, thực hiện:
- append := True
- Với mỗi j trong letters, thực hiện:
- append := append và (số lần j xuất hiện trong letters <= số lần j xuất hiện trong i)
- Nếu append là true, thì:
- Thêm i vào cuối valid_words
- Trả về từ có độ dài nhỏ nhất trong valid_words
Hãy xem 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