Слова из других слов

Сложная

Дан список различных слов dictionary. Найдите в нём все слова, которые можно целиком составить, приписав друг к другу хотя бы два других слова из этого же списка. Одно и то же слово можно использовать несколько раз. Верните найденные слова в любом порядке.

Пример 1

dictionary=['sun', 'flower', 'sunflower', 'pot', 'flowerpot', 'sunflowerpot', 'rain'] → ['sunflower', 'flowerpot', 'sunflowerpot']

sunflower = sun + flower, flowerpot = flower + pot, sunflowerpot = sun + flower + pot. Слово rain из других не складывается.

Пример 2

dictionary=['ha', 'hahaha', 'hah'] → ['hahaha']

hahaha = ha + ha + ha: одно и то же слово можно брать несколько раз. hah не собрать.

Пример 3

dictionary=['tree', 'house'] → []

Ограничения

1 ≤ len(dictionary) ≤ 10⁴
1 ≤ len(dictionary[i]) ≤ 30
Суммарная длина слов не больше 10⁵
Слова состоят из строчных латинских букв и не повторяются

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

Решили0

Пробовали0

Отправок0

Принято—

Темы

Depth-First Search Trie Array String Dynamic Programming

Вход

dictionary=['sun', 'flower', 'sunflower', 'pot', 'flowerpot', 'sunflowerpot', 'rain']

Ожидается

['sunflower', 'flowerpot', 'sunflowerpot']

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