Слова для головоломок

Сложная

В словесной игре каждая головоломка — строка из букв, первая из которых *ключевая*. Слово подходит к головоломке, если: - слово содержит ключевую букву головоломки; - каждая буква слова встречается в головоломке (буквы слова могут повторяться). Даны список слов words и список головоломок puzzles. Верните список, где на месте i стоит количество слов из words, подходящих к головоломке puzzles[i]. Слов очень много, головоломок тоже — проверять каждую пару слишком долго.

Пример 1

words=["tool", "lot", "loot", "stool", "too"], puzzles=["tlo", "otsl", "lot"] → [4, 5, 3]

Для "tlo" подходят tool, lot, loot и too (в stool есть s) — 4. Для "otsl" подходят все пять слов. Для "lot" ключевая буква l: too её не содержит, а в stool есть s — остаётся 3.

Пример 2

words=["bee", "beef"], puzzles=["fbe", "zbe"] → [1, 0]

"fbe" требует букву f — подходит только beef. Ключевая буква "zbe" — z, её нет ни в одном слове, поэтому 0.

Ограничения

1 ≤ len(words) ≤ 10⁵
1 ≤ len(words[i]) ≤ 50
1 ≤ len(puzzles) ≤ 10⁴
1 ≤ len(puzzles[i]) ≤ 7
Все строки состоят из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Bit Manipulation Trie Array Hash Table String

Вход

words=["tool", "lot", "loot", "stool", "too"], puzzles=["tlo", "otsl", "lot"]

Ожидается

[4, 5, 3]

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