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

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

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

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

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

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

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

Решение (TS):

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

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

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

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

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

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

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

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

Март 23, 2023 г.

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

Читать

Подсчет кол-ва нулевых подмассивов

Март 21, 2023 г.

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays). Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей. Например, дан массив [0, 0, 1]. Как видим, есть последовательность из двух нулей в начале ...

Читать

 

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

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



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