Я, кстати в C++ листах неразобрался
листах
Порридж В Ко-ливинге
Порридж В Ко-ливинге
если получится, поделись, плз, решением. любопытно посмотреть.
Так я и не доделал
Порридж В Ко-ливинге
Получалось с указателями, но там надо было уже прыгать и выходило больше N(O) доступов
Viktor
смешно, что на сегодняшнюю задачу я уже записывал видосик, незадолго до начала майского челенджа 😄
Viktor
довольно популярная задача похоже
Порридж В Ко-ливинге
Viktor
префиксное
Порридж В Ко-ливинге
А это нормально, если я его хочу сделать через кучу unordered_map ?
Viktor
да можно, конечно. попробовать стоит 🙂 а где именно ты хочешь там это использовать? чтобы хранить деток?
Иван
Мне тоже сегодня повезло. Решал её в рамках mock тренировки)
Иван
Просто сабмит сейчас сделал)
Viktor
я для этого использовал обычный вектор длины 26. все-таки алфавит ограничен.
Порридж В Ко-ливинге
Viktor
я для этого использовал обычный вектор длины 26. все-таки алфавит ограничен.
> You may assume that all inputs are consist of lowercase letters a-z
Порридж В Ко-ливинге
я для этого использовал обычный вектор длины 26. все-таки алфавит ограничен.
Там же у каждого будет еще вектора и еще и еще
Порридж В Ко-ливинге
Тогда пошел мучатся
Viktor
да вроде норм 🙂 ну через отдельную структурку Node надо делать.
Viktor
инкапсулировать немного.
Порридж В Ко-ливинге
Я такой нелегальный способ сделал решить сегодняшнюю
Порридж В Ко-ливинге
Ну она как я понял O(n*k)
Viktor
Ага
Viktor
Или расскажи
Evgeniy
А слова в Insert разные могут подаваться?
Evgeniy
Т.е. не обязательно с одним префиксом?
Порридж В Ко-ливинге
https://pastebin.com/JF8x1kb6
Viktor
Вроде, да. Никаких ограничений нет для этого.
Evgeniy
Вроде, да. Никаких ограничений нет для этого.
Понятно. А то по примерам выглядит будто все одинаково начинаются
Порридж В Ко-ливинге
Понятно. А то по примерам выглядит будто все одинаково начинаются
Уже давно надо было привыкнуть к примерам
Порридж В Ко-ливинге
Они не объясняющие так сказать
Evgeniy
Так и есть
Порридж В Ко-ливинге
Хотя никто не обещал исчерпывающих
Порридж В Ко-ливинге
Если в CodeForces аккуратно 2-3 разных случая рассказали
Порридж В Ко-ливинге
То тут вообще почти или одинаковый или закономерные случаи
Evgeniy
Там же у каждого будет еще вектора и еще и еще
И так сработало? Это первое, что мне в голову пришло
Evgeniy
Букв
Evgeniy
Да я всё про время думаю
Evgeniy
Вот и интересуюсь
Порридж В Ко-ливинге
Тут же однозначно O(N) O(N)
Порридж В Ко-ливинге
Ну я реализовал O(N^2) )0)
Evgeniy
Я думаю тут bfs
Порридж В Ко-ливинге
Опять деревья умные какие-то
Evgeniy
В худшем случае вообще все буквы переберём
Порридж В Ко-ливинге
Я раньше думал что bfs это Корейская группа такая
Viktor
Обычный мухлеж
Нормальная история. Мне только не нравится создание k * n новых строк, в худшем случае, где k - самое длинное слово. Собственно префиксные деревья ровно для этого и нужны, чтобы избавиться от этого.
Порридж В Ко-ливинге
Порридж В Ко-ливинге
А там колдуства происходят
Viktor
Задача - реализуйте префиксное дерево. Решение - это колдунство, поэтому вот вам другое решение 😃
Evgeniy
По памяти будет прям ого-го
Viktor
По памяти будет прям ого-го
Зато по времени О(1) если считать вычисление хеша от строки бесплатным 😆👍
Viktor
Зальём железом, че нам кабанам.
Viktor
Как говорят всякие Умпутуны.
Viktor
Отличная задача для собеседования, чтобы обсудить разные решения с разными сложностями.
Порридж В Ко-ливинге
Ээээээ
Порридж В Ко-ливинге
Друзья-товарищи
Порридж В Ко-ливинге
У кого мак и на маке стоит Телега?
Порридж В Ко-ливинге
Можете сказать, сколько у вас весит /Users/*user*/Library/Group Containers/*hash*.ru.keepcoder.Telegram/account-*hash*/postbox/media
Viktor
Порридж В Ко-ливинге
У меня резко появилось лишних 20 ГБ
Порридж В Ко-ливинге
https://medium.com/@eugene_lazarev/telegram-on-mac-os-takes-no-care-about-your-disk-storage-and-feels-great-about-it-2c62ded92924
Порридж В Ко-ливинге
Причем это даже не файлы