사전 단어가 있고 주어진 사전 단어에서 최소 길이 단어를 찾아야 한다고 가정합니다. 이 단어에는 licensePlate 문자열의 모든 문자가 있습니다. 이제 그런 단어가 주어진 문자열 licensePlate를 완성한다고 합니다. 여기서는 대소문자를 무시합니다. 그리고 답은 반드시 존재합니다. 답변이 둘 이상인 경우 배열에서 가장 먼저 발생한 답변을 반환합니다.
번호판에는 동일한 문자가 여러 번 나타날 수 있습니다. 따라서 "PP"의 licensePlate에서 "pile"이라는 단어가 licensePlate를 완성하는 것이 아니라 "topper"라는 단어가 완성됩니다.
따라서 입력이 licensePlate ="1s3 PSt", words =["step", "steps", "stripe", "stepple"]인 경우 출력은 다음을 포함하는 가장 작은 길이의 단어인 "steps"가 됩니다. 문자는 "S", "P", "S", "T"입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 알파벳 :="abcdefghijklmnopqrstuvwxyz"
- 문자:=s가 알파벳일 때 licensePlate에서 모든 s를 가져옴으로써 소문자로 된 s 목록
- valid_words :=새 목록
- 단어의 각 i에 대해 do
- 추가 :=참
- 문자의 각 j에 대해
- append :=추가 및 (문자의 j 수 <=i의 j 수)
- append가 참이면
- valid_words 끝에 i 삽입
- 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