394. Decode String

Prompt

Given an encoded string, return its decoded string.

Input: s = "3[a2[c]]"
Output: "accaccacc"
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

Approach

The scenarios in which there are no nested values are straightforward. We’ll primarily want to focus on the scenarios in which there are nested values and there are 2 — both of which are displayed below:

1st scenario: "3[a2[c6[d]]]"
2nd scenario: "3[a2[b]5[c]]"

Code

Python | Time: O(n * maxK^countK) | Space: O(sum(n * maxK^countK))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com