Шифр монстров
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
- Строки
- Словари и множества
У монстра есть словарь vocabulary из различных слов (строчные латинские буквы). Предложение — последовательность слов словаря, одно слово может повторяться. Монстр шифрует предложение так: перемешивает буквы в каждом слове случайным образом и убирает пробелы.
Для каждой строки из ciphers определите, сколько различных исходных предложений (последовательностей слов) могли дать эту строку. Верните список ответов в том же порядке, каждый по модулю 1000000007. Если подходящих предложений нет, ответ 0. Слова с одинаковым набором букв (например, "ab" и "ba") считаются разными словами.
Ограничения: слов в словаре до 400 длиной до 20, в ciphers до 5 строк длиной до 4000.
Пример: словарь ["this", "is", "a", "monster", "retsnom"], шифр "ishtsiarestmon" → 4 (is this a monster, is this a retsnom, this is a monster, this is a retsnom).
Источник: Coding Competitions Archive, kickstart/2016/round_d/codejamon_cipher · © Google LLC · Apache-2.0 · условие переведено и дополнено