Задача 394 с литкода. Дана строка, где присутствуют группы вроде N[string], нужно раскрыть скобки, повторяя строку внутри скобок N раз. Структуры могут быть вложенными.
Чтобы выработать решение, рассмотрим пример:
|
1 |
"2[a3[c]]" |
Можно раскрывать скобки в любом порядке, результат не изменится:
|
1 2 |
"2[a3[c]]" -> a3[c]a3[c] -> acccaccc "2[a3[c]]" -> 2[accc] -> acccaccc |
Второй вариант, наверное, проще реализовать.
Задача сводится к тому, чтобы найти в строке шаблон N[decoded_string], где decoded_string не содержит скобок, и выполнить подстановку N * decoded_string. Т.к. шаблоны могут быть вложенными, то после подстановки мы уменьшим существующую вложенность кодированной строки. Но операцию придется выполнять, пока на очередной итерации не останется искомого шаблона.
JS, на котором я обычно решаю задачки, содержит нужные нам функции и для замены по шаблону и для вычисления N * decoded_string.
Решение (TS):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
function decodeString(s: string): string { // нужен бесконечный цикл, // чтобы принять решение об остановке по ходу решения while (true) { // флажок будет сигнализировать о том, были ли // произведены подстановки на этой итерации цикла let flag = false; // воспользуемся функцией String.replace с регуляркой и колбеком s = s.replace(new RegExp(/(\d+)\[(\w+)\]/g), // кол-бек функция настроена на прием двух переменных из шаблона // nStr принимает (\d+) // word принимает (\w+) // остается только "перемножить" (s: string, nStr: string, word: string): string => { flag = true // <em>N * decoded_string</em> return word.repeat(parseInt(nStr)) } ); if (!flag) break; } return s; }; |
Регулярные выражения — это своеобразная тяжелая артиллерия. Там где скорость не является критичным фактором для приложения, там можно смело их использовать.
А нашу задачу можно решить и более легкими средствами.
Возвращаясь к примеру, можно попробовать анализировать строку символ за символом и следовать логике кодировки. У нас возникает несколько ситуаций:
- символы 0 — 9: мы не знаем будет ли за числом сразу идти скобка, т.к. строка рассматривается посимвольно. Потому нужно где то аккумулировать число, авось потом пригодится.
- Скобка ‘[‘ открывашка — в этот момент надо запомнить число перед скобкой и уже собранную строку, чтобы внутри скобок можно было снова собирать и строку и число. Т.к. скобки вложенные, то сохранять значения удобно на стеке.
- Скобка ‘]’ закрывашка — в этот момент надо взять со стека множитель, собранную строку умножить на этот множитель и прибавить всё к той строке, которую мы сохраняли на стеке.
- буквы ‘a’ — ‘z’: их мы просто аккумулируем.
Так можно декодировать строку без сложных объектов вроде регулярных выражений. Придется, конечно, написать больше кода, чем в прошлый раз (typescript).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
function decodeString(s: string): string { // это стек значений // там будем хранить и строки и числа const stack: (number | string)[] = []; // аккумуляторы числа и строки let num = 0, res = ''; for (let i = 0; i < s.length; i ++) { // перебираем символы и реализуем кейсы const char = s[i] if (char >= '0' && char <= '9') { num = num * 10 + parseInt(char); } else if (char == '[') { stack.push(res) stack.push(num) res = ''; num = 0; } else if (char == ']') { // закрывашка: // получим множитель const count: number = stack.pop() as number; // соберём строку res = stack.pop() as string + res.repeat(count) num = 0; } else { res += char; } } return res; }; |