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

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

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

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

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

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

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

Решение (TS):

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

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

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

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

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

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

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

Задача о наибольшей сумме монет

Апрель 15, 2023 г.

Решаем задачу № 2218 с leetcode - Maximum Value of K Coins From Piles. В названии фигурирует слова монеты и стопки. Если представить себе, что монеты могут быть произвольного номинала, то да - суть именно такая. У нас есть стопки монет, и дано число ...

Читать

Игра в камни

Май 27, 2023 г.

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

Читать

 

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

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



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