Декодировка строки

Задача 394 с литкода. Дана строка, где присутствуют группы вроде N[string], нужно раскрыть скобки, повторяя строку внутри скобок N раз. Структуры могут быть вложенными.

Чтобы выработать решение, рассмотрим пример:

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

Второй вариант, наверное, проще реализовать.

Задача сводится к тому, чтобы найти в строке шаблон N[decoded_string], где decoded_string не содержит скобок, и выполнить подстановку N * decoded_string. Т.к. шаблоны могут быть вложенными, то после подстановки мы уменьшим существующую вложенность кодированной строки. Но операцию придется выполнять, пока на очередной итерации не останется искомого шаблона.

JS, на котором я обычно решаю задачки, содержит нужные нам функции и для замены по шаблону и для вычисления N * decoded_string.

Решение (TS):

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

А нашу задачу можно решить и более легкими средствами.

Возвращаясь к примеру, можно попробовать анализировать строку символ за символом и следовать логике кодировки. У нас возникает несколько ситуаций:

  • символы 0 — 9: мы не знаем будет ли за числом сразу идти скобка, т.к. строка рассматривается посимвольно. Потому нужно где то аккумулировать число, авось потом пригодится.
  • Скобка ‘[‘ открывашка — в этот момент надо запомнить число перед скобкой и уже собранную строку, чтобы внутри скобок можно было снова собирать и строку и число. Т.к. скобки вложенные, то сохранять значения удобно на стеке.
  • Скобка ‘]’ закрывашка — в этот момент надо взять со стека множитель, собранную строку умножить на этот множитель и прибавить всё к той строке, которую мы сохраняли на стеке.
  • буквы ‘a’ — ‘z’: их мы просто аккумулируем.

Так можно декодировать строку без сложных объектов вроде регулярных выражений. Придется, конечно, написать больше кода, чем в прошлый раз (typescript).

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

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

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

Июнь 7, 2023 г.

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

Читать

Поиск выхода из лабиринта

Июнь 3, 2023 г.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так - дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, ...

Читать

 

Комментарии к «Декодировка строки»

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



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