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

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

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

Вычисление заголовка столбца в Excel

Март 23, 2023 г.

Leetcode задача #168. Excel Sheet column title.Задача помечена как простая, тем не менее, не сразу понял как её решать. Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, ...

Читать

Задача о поиске лучшей сделки

Февраль 2, 2023 г.

Это еще одна классическая задача программирования о поиске некой лучшей пары чисел в массиве. Задача формулируется следующим образом. Есть массив стоимости ...

Читать

 

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

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



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