Почему это работает
- Слово хранится путём из букв от корня, поэтому все слова с одинаковым началом проходят через одни и те же узлы, и find доходит до узла любого префикса за столько шагов, сколько в нём букв.
- Дойти до узла — значит только, что какое-то слово так начинается. Целому слову нужна своя отметка конца: в этом вся разница между search и startsWith.
- У слова, которое служит началом более длинного, как «to» у «top», путь уже есть. Вставка не добавляет узлов, а только ставит отметку.
Сложность
Время O(L) на вызов, где L — длина его слова: по шагу на букву. Память O(суммы длин вставленных слов): не больше узла на букву и меньше, когда у слов общее начало.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗