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

Средняя

medium , string , recursion

12 February 2024

Описание задачи #

Вам дана закодированная строка, верните ее декодированную версию.

В строке используется следующее правило кодирования: k[encoded_string], означает что закодированная внутри квадратных скобок строка должна повторяться ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.

При этом входная строка всегда гарантированно валидная, то есть в ней нет лишних пробелов и квадратные скобки имеют правильную форму. Кроме того, цифры в строке предназначены только для повторяющихся чисел k. Например, не будет ввода типа 3a или 2[4].

Обратите внимание на то, что закодированные строки могут вкладываться друг в друга.

Ограничения #

Длина входной строки находится в диапазоне от 1 до 30
Входная строка содержит только латинские буквы в нижнем регистре, цифры и квадратные скобки
Входная строка всегда валидная
Значения k находятся в диапазоне от 1 до 300
Длина результирующей строки не превышает 10⁵

Примеры #

Входные данные: "3[a]2[bc]"

Ответ: "aaabcbc"
Входные данные: "3[a2[c]]"

Ответ: accaccacc
Входные данные: "2[abc]3[cd]ef"

Ответ: "abcabccdcdcdef"

Решение #

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

Создаем результирующую пустую строку, которая будет использоваться для накопления декодированного результата.
Далее перебираем строку посимвольно и проверяем следующие условия:

Если текущий символ является буквой (от 'a' до 'z'), добавляем его в результат res и переходим к следующему символу.
Если встречается цифра, это означает начало закодированного блока. Число перед [ (количество повторений) считывается посимвольно. Так как k может быть многозначным числом, используется накопление count в цикле, где каждая новая цифра добавляется к count с учетом ее разрядности (умножение на 10).

После определения count и нахождения открывающей скобки [, алгоритм ищет соответствующую закрывающую скобку ]. Это делается с помощью счетчика bracket, который увеличивается при нахождении [ и уменьшается при нахождении ], позволяя обрабатывать вложенные скобки.
Как только найдена соответствующая закрывающая скобка, вырезается подстрока между [ и ] и для нее рекурсивно вызывается функция decodeString. Результат этого вызова повторяется count раз и добавляется к итоговому результату res.
Индекс i устанавливается на позицию закрывающей скобки, чтобы продолжить обход строки после обработанного блока.

Реализация #

package decode_string

import "strings"

func decodeString(s string) string {
	res := ""

	for i := 0; i < len(s); i++ {
		if s[i] >= 'a' && s[i] <= 'z' {
			res += string(s[i])
			continue
		}

		count := 0
		for s[i] != '[' {
			count = count*10 + int(s[i]-'0')
			i++
		}

		bracket := 1
		j := i + 1
		for bracket > 0 {
			if s[j] == '[' {
				bracket++
			}

			if s[j] == ']' {
				bracket--
			}

			j++
		}

		res += strings.Repeat(decodeString(s[i+1:j-1]), count)
		i = j - 1
	}

	return res
}

export const decodeString = (s: string): string => {
    let res = ""

    for (let i = 0; i < s.length; i++) {
        if (s[i] >= 'a' && s[i] <= 'z') {
            res += s[i]
            continue
        }

        let count = 0
        while (s[i] != '[') {
            count = count*10 + Number(s[i])
            i++
        }

        let bracket = 1
        let j = i + 1
        while (bracket > 0) {
            if (s[j] == '[') {
                bracket++
            }

            if (s[j] == ']') {
                bracket--
            }

            j++
        }

        res += decodeString(s.substring(i+1, j-1)).repeat(count)

        i = j - 1
    }

    return res
}

Оценка сложности #

По времени

O(max^k * n), где max^k — максимальное значение k, а n — длина данной строки s.

По памяти

O(n) — это пространство, используемое для хранения внутреннего стека вызовов для рекурсии. Поскольку мы рекурсивно декодируем каждый вложенный шаблон, максимальная глубина стека рекурсивных вызовов не будет превышать n.

Оригинал задачи на Leetcode

Algorithmics