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 в коде).

Написать комментарий

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

Результат k-ой перестановки

Июль 5, 2023 г.

Очередная задача с литкода (№60. Permutation Sequence). В общем случае формулируется так: дан набор элементов, требуется вернуть этот набор после k перестановок. ...

Читать

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

Июнь 25, 2023 г.

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

Читать

 

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

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



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