Мне с моим скромным прогрессом даже както стыдно немного :(

Мне с моим скромным прогрессом даже както стыдно немного :(

С работой и детьми на самом деле не так просто это дело совмещается. Хочется часа 2-3 алгоритмить, получается час + еще разборы смотрю

Мне с моим скромным прогрессом даже както стыдно немного :(

Приватные репо не считаются же, поэтому у меня все хорошо ))

С работой и детьми на самом деле не так просто это дело совмещается. Хочется часа 2-3 алгоритмить, получается час + еще разборы смотрю

Happy Monday! 👋 На этой неделе разбираем классический пример задачи на графы и обход в ширину, где как раз нужны очереди. https://vitkarpov.me/posts/word-ladder/

Happy Monday! 👋 На этой неделе разбираем классический пример задачи на графы и обход в ширину, где как раз нужны очереди. https://vitkarpov.me/posts/word-ladder/

Привет! Есть некоторая мысль по поводу этой задачи, но я не совсем в ней уверен. В твоей реализации ты сначала строишь граф за O(N^2), а потом начинаешь его обходить за O(N). Если же предположить, что в wordList будут "лишние" слова (отличающиеся более, чем на 1 символ, а значит не интересные нам), то нам всё равно придётся их проверять. Предположение моё заключается в том, что мы можем искать соседей на лету, перед отправкой в очередь. В худшем случае, если все слова потенциально нам подходят, мы получим ровно тот же O(N^2). Если же в wordList много мусора, то это может нам выиграть время. Впрочем, есть ощущение, что на leetcode нет таких кейсов. Я тоже сначала строил граф, а потом попробовал "оптимизировать", время при этом не меняется.

Вообще можно фолоуапом добавить решение O(W * R), где W - длина слова, а R - результат (< N). В итоге почти всегда будет быстрее O(N^2) решения + покажем чтотдля обшода в ширину можно использовать сеты)

Привет! Есть некоторая мысль по поводу этой задачи, но я не совсем в ней уверен. В твоей реализации ты сначала строишь граф за O(N^2), а потом начинаешь его обходить за O(N). Если же предположить, что в wordList будут "лишние" слова (отличающиеся более, чем на 1 символ, а значит не интересные нам), то нам всё равно придётся их проверять. Предположение моё заключается в том, что мы можем искать соседей на лету, перед отправкой в очередь. В худшем случае, если все слова потенциально нам подходят, мы получим ровно тот же O(N^2). Если же в wordList много мусора, то это может нам выиграть время. Впрочем, есть ощущение, что на leetcode нет таких кейсов. Я тоже сначала строил граф, а потом попробовал "оптимизировать", время при этом не меняется.

Не очень уловил, можно чуть подробнее?

Загрузил все строки в Set, а потом в ищешь в ширину, но не идя по Set и проверяя, а меняя букву одну и смотря, есть ли онив Set

Загрузил все строки в Set, а потом в ищешь в ширину, но не идя по Set и проверяя, а меняя букву одну и смотря, есть ли онив Set

Идея норм, т.е. идёшь по всем словам, в каждом из них пробуешь 26 вариантов различных букв в каждой позиции и смотришь в сет, если нашлось слово — это возможный переход, а как сам путь искать?

зачем 26? ты можешь загрузить все буквы в отдельный сет и по нему только идти )

так это, всё равно надо перебрать все буквы, не?

Идея норм, т.е. идёшь по всем словам, в каждом из них пробуешь 26 вариантов различных букв в каждой позиции и смотришь в сет, если нашлось слово — это возможный переход, а как сам путь искать?

Зачем нам путь. Просто считаем каждый "переход" в глубину ширину

Там же кратчайший нужно путь найти. Обходя в ширину ты его гарантированно найдёшь, не перебирая все пути.

Ой, обход в ширину. Нам не надо пути переьирать все

А как искать соседей на лету? Скажем у нас одно слово в начале списка, а другое в конце, и оба отличаются на один символ.

А точно так же, как и в buildGraph - его внутренним циклом. Вот, в чем вижу проблему: ["hot","dot","dog","lot","log","cog","aaa","bbb","zzz"] { hit: ['hot'], hot: ['dot','lot'], dot: ['dog','lot'], dog: ['log','cog'], lot: ['log'], log: ['cog'], aaa: [], bbb: [], zzz: [], } В buildGraph мы для aaa, bbb, zzz переберем все остальные слова, чтобы проверить нет ли у них соседей. В моём варианте мы их вообще трогать не будем. Начали с первого слова, прошлись циклом, получили hot. Дальше ищем соседей для hot и т.д. В итоге лишняя работа не будет произведена.

Ага, ясно. Не понял как в ширину ты обходишь пока.

Загрузил все строки в Set, а потом в ищешь в ширину, но не идя по Set и проверяя, а меняя букву одну и смотря, есть ли онив Set

О, прям честный граф строится. А я как всегда эту задачку через сеты решал. Вообще сеты вещь опупенная)

Честный граф, чтобы показать, что это граф, да. Я понял, ты строишь его «на лету», не складывая в отдельный словарь, а сразу в очередь.

Оказалось я делал это на плюсах, т.к. строки мутабельный https://pastebin.com/wNH4VSzV

Да мог просто сплитнуть строку в массив и там менять сколько влезет.

А точно так же, как и в buildGraph - его внутренним циклом. Вот, в чем вижу проблему: ["hot","dot","dog","lot","log","cog","aaa","bbb","zzz"] { hit: ['hot'], hot: ['dot','lot'], dot: ['dog','lot'], dog: ['log','cog'], lot: ['log'], log: ['cog'], aaa: [], bbb: [], zzz: [], } В buildGraph мы для aaa, bbb, zzz переберем все остальные слова, чтобы проверить нет ли у них соседей. В моём варианте мы их вообще трогать не будем. Начали с первого слова, прошлись циклом, получили hot. Дальше ищем соседей для hot и т.д. В итоге лишняя работа не будет произведена.

Реализовал эту идею, получилось ещё медленнее 😂 Из-за постоянного создания строк. Ну, понятно дело, что там тесты так подобраны, что нет «лишних слов».

Реализовал эту идею, получилось ещё медленнее 😂 Из-за постоянного создания строк. Ну, понятно дело, что там тесты так подобраны, что нет «лишних слов».

Забыл уточнить, что я исключительно индексами оперировал, а не строками :) https://github.com/SlivTime/leetcode/blob/master/src/127-word-ladder/word_ladder.go#L17

Забыл уточнить, что я исключительно индексами оперировал, а не строками :) https://github.com/SlivTime/leetcode/blob/master/src/127-word-ladder/word_ladder.go#L17

Happy Monday! 👋 На этой неделе разбираем классический пример задачи на графы и обход в ширину, где как раз нужны очереди. https://vitkarpov.me/posts/word-ladder/

> Мы смотрим на деток Статья написана отцом

> Мы смотрим на деток Статья написана отцом

просто если делать эту историю с сетами все равно ж придётся генерировать горы строк, чтобы их сравнивать с тем, что в списке

На жс задачка весело решается в три строки ))

Без дополнительный памяти?

все модификации только исходного массива

Go

Реализовал эту идею, получилось ещё медленнее 😂 Из-за постоянного создания строк. Ну, понятно дело, что там тесты так подобраны, что нет «лишних слов».

В плбсах такой вот проблемы нет. Монжо еще сравнение убрать, чтобы было настгящее O(R * W) а не O(R * (W^2)) под капотом. Но это головняк

на го никто не решает 😃

Мне приятнее думать, что я самый быстрый стрелок на диком западе :)

Всем привет 👋 Подскажите пожалуйста кто знает как можно локально мерить рантайм перформанс чтобы он +/- совпадал с тем что показывает leetcode ?

Я понял, значит каждый раз руками

что значит руками?

написать плагин, который будет по апи лазить в литкод ))

я не смог найти как он запросы отправляет. как такое возможно? 😄

может фильтр какой стоит в network?