43 lines
1.4 KiB
Python
43 lines
1.4 KiB
Python
# yigid balaban <fyb@fybx.dev>
|
|
# neetcode 2024
|
|
# easy / shortest completing word
|
|
|
|
def solution(licensePlate: str, words: list[str]) -> str:
|
|
licensePlate = ''.join([c.lower() for c in licensePlate if not c.isdigit()]).replace(' ', '')
|
|
words = sorted(words, key=len)
|
|
scores = []
|
|
|
|
pw = 0
|
|
lp = licensePlate
|
|
score = 0
|
|
while True:
|
|
for c in words[pw]:
|
|
if c in lp:
|
|
score += 1
|
|
lp = lp.replace(c, '', 1)
|
|
if len(lp) == 0:
|
|
return words[pw]
|
|
scores.append(score)
|
|
score = 0
|
|
lp = licensePlate
|
|
pw += 1
|
|
|
|
if pw >= len(words):
|
|
break
|
|
|
|
smallest_first = 0
|
|
for ps in range(len(scores) - 1, -1, -1):
|
|
if scores[ps] >= scores[smallest_first]:
|
|
smallest_first = ps
|
|
return words[smallest_first]
|
|
|
|
|
|
print(solution("1s3 PSt", ["step","steps","stripe","stepple"]) == "steps")
|
|
print(solution("1s3 456", ["looks","pest","stew","show"]) == "pest")
|
|
print(solution("GrT 390b7", ["trobbg", "robotgrt", "gtrb"]) == "gtrb")
|
|
print(solution("q4L Mx37 o", ["loxm", "qlmox", "mloxq"]) == "qlmox")
|
|
print(solution("A1B2C3", ["abccdef", "bcabc", "aabbcc", "cbca"]) == "cbca")
|
|
print(solution("M6k39 Jdf 21", ["mfkjd", "mkfjddd", "mjjkfd", "jfdmk"]) == "mfkjd")
|
|
print(solution("Th9X9er5", ["thexer", "therxx", "xether", "thxere"]) == "thexer")
|
|
|