Декодируйте строку, рекурсивно закодированную как count, за которой следует подстрока | Набор 2 (с использованием рекурсии)

Опубликовано: 20 Сентября, 2022

Дана закодированная строка str . Шаблон, в котором кодируется строка, выглядит следующим образом.

<count>[sub_str] ==> The substring ‘sub_str’ appears count times.

Задача состоит в том, чтобы декодировать эту строку str .

Примеры:

Input: str = “1[b]”
Output: b
Explanation: The substring ‘b’ is repeated 1 time.

Input: str = “2[ab]”
Output: abab
Explanation: The substring “ab” is repeated two times.

Input: str = “2[a2[b]]”
Output: abbabb
Explanation: The substring ‘b’ is repeated 2 times and added to ‘a’ which forms a substring “abb”. 
Now this substring is repeated two time. So the final string is “abbabb”.

Итеративный подход: Итеративный подход упоминается в Set-1 этой проблемы.

Рекурсивный подход: в этой статье проблема будет решена с использованием рекурсии и стека. Следуйте подходу, указанному ниже, чтобы решить проблему

  • Объявить стек
  • Рекурсивно пройти каждый символ данной строки один за другим. Может быть 4 случая:
    • Случай 1: Текущий символ '['
      • В этом случае ничего делать не нужно. Просто перейдите к следующему символу
    • Случай 2: Текущий символ ']'
      • Извлеките верхнюю временную строку и верхнее целое число x из стека
      • Повторите строку temp, x раз
      • Если следующий верхний элемент в стеке является строкой, добавьте эту повторяющуюся строку к верхней строке
      • иначе поместите повторяющуюся строку в стек
    • Случай 3: Текущий символ — цифра
      • Если предыдущий символ исходной строки также был цифрой, добавьте эту цифру к числу на вершине стека.
      • Если предыдущий символ был чем-то другим, поместите эту цифру в стек
    • Случай 4: Текущий символ — это алфавит
      • Если предыдущий символ исходной строки также был алфавитом, добавьте этот алфавит к строке наверху стека.
      • Если предыдущий char был чем-то другим, поместите этот алфавит в стек
  • В конце верните строку в стек и распечатайте ее

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N), где N — длина декодированной строки.
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ