Задачник по алгоритмам

Программа курса:

Задача 15: Кратчайшее завершающее слово

Напишите определение функции
def shortestCompletingWord(licensePlate: str, words: list[str]) -> str,
которая принимает два аргумента:

  1. licensePlate (строка) — текст, содержащий буквы, цифры и пробелы. Игнорируйте цифры и пробелы, рассматривайте буквы без учета регистра.
  2. words (список строк) — массив слов, среди которых нужно найти кратчайшее подходящее слово.

Задача:
Найдите самое короткое подходящее слово (completing word) из массива words.

Подходящее слово — это слово, которое содержит все буквы из licensePlate, при этом:

  • Игнорируются цифры и пробелы в licensePlate.
  • Регистр букв не учитывается.
  • Если буква встречается в licensePlate несколько раз, то она должна встречаться в слове не меньше этого количества.

Если подходящих слов несколько, верните то, которое встречается раньше в списке words.

Примеры:

Пример 1:
Ввод:
licensePlate = "1s3 PSt"
words = ["step", "steps", "stripe", "stepple"]

Вывод:
"steps"

Объяснение:
licensePlate содержит буквы 's', 'p', 's' (без учета регистра) и 't'.

  • "step" содержит буквы 't' и 'p', но только одну 's'.
  • "steps" содержит все нужные буквы: 't', 'p', 's' (дважды).
  • "stripe" не содержит второй буквы 's'.
  • "stepple" не содержит второй буквы 's'.
    Правильный ответ: "steps".

Пример 2:
Ввод:
licensePlate = "1s3 456"
words = ["looks", "pest", "stew", "show"]

Вывод:
"pest"

Объяснение:
licensePlate содержит только букву 's'.
Все слова содержат букву 's', но самыми короткими являются "pest", "stew" и "show".
Из этих слов "pest" встречается первым, поэтому ответ: "pest".

Гарантируется:
Ответ всегда существует.

0
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии