Префиксное дерево

Реализуйте хранилище слов (префиксное дерево) и выполните над ним список операций. Хранилище сначала пусто. Слова состоят из строчных латинских букв и не пусты.

Операция operations[i] применяется к слову values[i]:

• insert — добавляет слово в хранилище (повторное добавление ничего не меняет); результат — false;
• search — результат true, если в хранилище есть именно это слово целиком;
• starts_with — результат true, если в хранилище есть хотя бы одно слово, которое начинается с values[i] (само слово тоже считается своим префиксом).

Верните список результатов, по одному на операцию. Операций не больше 10 000.

Пример: операции ["insert", "search", "search", "starts_with"], слова ["apple", "apple", "app", "app"] → [false, true, false, true].

Источник: задача CodeShare