Ctrl K

Плюс одна буква

Средняя
Даны два списка слов: base_words и goal_words. Во всех словах буквы не повторяются. Слово из goal_words достижимо, если его можно получить из какого-нибудь слова base_words так: 1. дописать в конец одну строчную латинскую букву, которой в слове ещё нет; 2. переставить буквы получившегося слова в любом порядке (в том числе оставить как есть). Сами списки при этом не меняются: каждое слово goal_words проверяется независимо. Верните, сколько слов в goal_words достижимы.
Пример 1
base_words=["rat", "pen", "lo"], goal_words=["tarp", "pen", "owl", "open"] → 3

"tarp" = "rat" + p, "owl" = "lo" + w, "open" = "pen" + o, буквы переставлены. "pen" уже есть среди исходных, но букву добавить обязательно, поэтому он не считается. Ответ 3.

Пример 2
base_words=["ab"], goal_words=["abcd", "b", "bca"] → 1

"abcd" длиннее на две буквы, "b" короче. Подходит только "bca". Ответ 1.

Пример 3
base_words=["x", "yz"], goal_words=["zy", "xyz", "wx"] → 2
Ограничения
  • 1 ≤ len(base_words), len(goal_words) ≤ 5 · 10⁴
  • 1 ≤ длина каждого слова ≤ 26
  • Слова состоят из строчных латинских букв
  • Внутри одного слова буквы не повторяются
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиРазложить анаграммы по группам СредняяПодпоследовательность только одного слова СредняяСамые частые запросы СредняяСлово, выращенное по букве СредняяСклеить карточки контактов Средняя
загружаем Python…
Вход
base_words=["rat", "pen", "lo"], goal_words=["tarp", "pen", "owl", "open"]
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 49 тестов на сервере, включая скрытые.