Neetcode | Decode String

В этой статье рассмотрим решение одной алгоритмической задачки под названием «Decode string».

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

На вход даётся закодированная строка. Правило кодирования простое: k[encoded_string]. Это означает, что строку encoded_string нужно повторить k раз. Скобки могут быть вложенными.

На примере строки 2[a3[b]]c

1. сначала разбираем 3[b] = bbb
2. получаем 2[abbb]c
3. затем 2[abbb] = abbbabbb
4. и в конце добавляем c
5. Итог: abbbabbbc

Ограничения по условию:

• k — всегда положительное целое
• скобки всегда корректны
• нет конструкций типа 3a или a[2]
• итоговая строка не длиннее 100 000 символов

Решение

Главная сложность — вложенность. Внутри одной пары скобок может быть ещё одна пара, и так несколько уровней. Самый естественный способ решить такую задачу — использовать стек. Причём стеков понадобится два: один для чисел (коэффициентов повтора), другой для строк.

Алгоритм решения

1. Идём по строке слева направо, обрабатывая каждый символ.
2. Если символ — цифра — накапливаем текущее число (цифры могут идти подряд, образуя многозначное число).
3. Если символ — буква — накапливаем текущую строку.
4. Если символ — [ — сохраняем текущую строку и текущее число в стеки, затем сбрасываем их для обработки нового уровня вложенности.
5. Если символ — ] — извлекаем из стеков предыдущее число k и предыдущую строку prev. Повторяем текущую строку k раз и приклеиваем её к prev. Это становится новой текущей строкой.

В конце остаётся текущая строка — это и есть декодированный результат.

О-большое

Время: O(n × m), где n — длина входной строки, m — максимальный коэффициент повтора. На практике все символы обрабатываются один раз, а повторение строк выполняется суммарно за O(длина выхода). Так как длина выхода не превышает 100 000, это эффективно.

Память: O(n) под стеки и промежуточные строки.

Решение на Go

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

package main

import (
	"strings"
	"unicode"
)

func decodeString(s string) string {
	stackLetters := []string{} // Стек для накопления строк
	stackNums := []int{}       // Стек для коэффициентов повтора (чисел)
	currentStr := ""           // Текущая накапливаемая строка
	currentNum := 0            // Текущее накапливаемое число

	for _, ch := range s {
		switch {

		// Если буква — просто добавляем к текущей строке
		case unicode.IsLetter(ch):
			currentStr += string(ch)

		// Если цифра — накапливаем число.
		// Это важно для многозначных чисел: например, "12" сначала даст 1, потом 12.
		// int(ch-'0') преобразует символ цифры в её числовое значение (от 0 до 9)
		case unicode.IsDigit(ch):
			currentNum = currentNum*10 + int(ch-'0')

		// Открывающая скобка — сохраняем текущую строку и текущее число в стеки
		case ch == '[':
			stackLetters = append(stackLetters, currentStr)
			stackNums = append(stackNums, currentNum)

			// Сбрасываем текущие значения для нового уровня вложенности
			currentStr = ""
			currentNum = 0

		// Закрывающая скобка — извлекаем из стеков предыдущие значения
		// Извлекаем последнее число
		case ch == ']':
			k := stackNums[len(stackNums)-1]
			stackNums = stackNums[:len(stackNums)-1]

			// Извлекаем предыдущую строку (которая была до открывающей скобки)
			prev := stackLetters[len(stackLetters)-1]
			stackLetters = stackLetters[:len(stackLetters)-1]

			// Повторяем currentStr k раз и приклеиваем к prev
			currentStr = prev + strings.Repeat(currentStr, k)
		}
	}

	// После обработки всей строки currentStr содержит полностью расшифрованный результат
	// просто возвращаем его
	return currentStr
}

func main() {
	// Проверка из примера
        fmt.Println(decodeString("2[a3[b]]c"))     // "abbbabbbc"
	fmt.Println(decodeString("axb3[z]4[c]"))   // "axbzzzcccc"
	fmt.Println(decodeString("ab2[c]3[d]1[x]")) // "abccdddx"
}