87. Scramble string — задача о перетасованных строках

Решаем задачу с литкода о перетасовке строки.

Даны две строки, нужно определить является ли вторая строка результатом перетасовки букв в первой. Правила перетасовки следующие:

Мы произвольно делим строку на две подстроки, которые обозначим SX и SY. Далее мы можем переставить SX и SY местами, а можем не делать этого. Алгоритм может повторяться для SX и SY, до тех пор, пока строку можно еще разделить.

Например, для baloon и onloba — наша функция должна выдать true. Т.к. мы можем сначала поделить строку на ‘ba’ и ‘loon’, переставить их местами, а потом то же самое проделать с ‘loon’ — разделить на ‘lo’ и ‘on’ и тоже переставить местами.

Другой пример — baloon и oblona — здесь функция должна выдать false, т.к. с помощью указанных выше правил перетасовки, мы не можем из 1й строки получить 2ю.

Решение

На leetcode в едитории подробно расписывается решение, основанное на методе динамического программирования. Это типичный подход для решения рекурсивных задач, но из-за многомерности пространства решения (число измерение больше 2) довольно сложно его понять, потому здесь я покажу решение с помощью рекурсии и мемоизации.

Рекурсия

Рекурсия следует прямо тем правилам, которые заданы задачей, их нужно только аккуратно запрограммировать.

Мы делим строку (изначально это S1) разными способами, и проверяем не является ли в свою очередь каждая подстрока результатом перетасовки. При этом мы проверяем два случая — с перестановкой частей строки и без этой операции. Нам нужно также знать позицию подстроки учитывая перестановки.

Когда длина подстроки будет равна 1, то нам нужно будет проверить не находится ли точно такой же символ на той же позиции в строке s2.

Звучит довольно просто, посмотрим код (typescript).

Код рабочий. Но понятно, что мы можем его оптимизировать.

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

Например, если вернуться к примеру с baloon и onloba , то мы можем разбить строку S1 на ‘bal’ и ‘oon’. Нет необходимости продолжать рекурсию для этих подстрок, так как очевидно, что подстроки S2 — ‘onl’, ‘oba’ не содержат тех же символов. И как бы мы не перетасовывали ‘bal’ , то не получим ‘onl’.

Это существенно ускоряет перебор, особенно для неглубокой перетасовки. Мы отсекаем ветки рекурсии с заведомо неправильным набором букв.

Для глубокой перетасовки этого мало, нужно как то оптимизировать ситуации, когда мы проверяем одинаковые подстроки, входя в разные ветки рекурсии. Например, разбивая baloon, мы получим подстроку ‘oon’ при разбиении [bal] — [oon] и при разбиении [ba]-[loon] -> [ba]-[[l]-[oon]].

Можно создать кеш, в котором мы будем, к примеру, запоминать результат проверки подстроки S в позиции POS, так мы отсечем уже ранее вычисленные результаты проверок.

Кеширование и использование встроенного объекта Map для организации кеша, позволяет существенно увеличить скорость перебора.

Алгоритм «не хватает звезд с неба», но даже по статистике leetcode выдаёт не плохие результаты.

Видно, что кеш требует в среднем больше памяти, чем другие алгоритмы, но не плохо справляется с задачей в смысле быстродействия. Если потребуется, то мы можем пожертвовать частью быстродействия и сократить расходы памяти, для этого можно убрать одну или несколько точек кеширования (их 4 в коде).

Мало букафф? Читайте есчо !

Задача о неперекрывающихся интервалах

Июнь 7, 2023 г.

Задачи об интервалах легко решаются перебором. Но если элементов много, то нужно сообразить в каком порядке их лучше перебирать, чтобы избежать лишних вычислений. Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами ...

Читать

Решение задачи оптимизации в направленном графе

Апрель 9, 2023 г.

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как "Largest Color Value in a Directed Graph". Суть задачи: дан направленный ...

Читать

Задача: подсчета кол-ва возможных маршрутов

Июнь 25, 2023 г.

Решаем задачу с литкода №1575 Count All Possible Routes. Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым ...

Читать

Игра в камни

Май 27, 2023 г.

Серия задач StoneGame на leetcode - образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого. Но это не наш случай, т.к. по условию ...

Читать
 

Комментарии к «87. Scramble string — задача о перетасованных строках»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: