Decode String

Problem Statement

In this problem, we are provided with an encoded string where the encoding follows a specific pattern: k[encoded_string]. The encoded string within the square brackets should be repeated k times, where k is a positive integer. The challenge is to decode this string according to the aforementioned rule. The input string lacks any irregular formatting—it does not contain any unnecessary whitespace, all square brackets are correctly paired, and it only uses digits to denote repetition counts. Moreover, the original message (before encoding) does not feature any numerical characters; numbers appear exclusively as repeat-specifiers. Each encoded string will also adhere to constraints ensuring outputs that are feasible to handle, both in length and complexity.

Examples

Example 1

Input:

s = "3[a]2[bc]"

Output:

"aaabcbc"

Example 2

Input:

s = "3[a2[c]]"

Output:

"accaccacc"

Example 3

Input:

s = "2[abc]3[cd]ef"

Output:

"abcabccdcdcdef"

Constraints

• 1 <= s.length <= 30
• 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 and Intuition

To decode the given encoded strings, we can follow a systematic approach that involves:

1. Using a stack data structure to handle the nested and sequential pattern described by the encoding rule. We utilize this stack to build the decoded string as we progress through the input.
2. Iterating through the input string character by character, handling different types of characters (digits, letters, and brackets) appropriately:
   • For digits: These signify the number of times the following string should be repeated. Multiple digits in sequence should be combined to form the complete multiplier (e.g., "12" should be interpreted as 12).
   • For letters: These are the base characters of our strings that will need to be repeated as per the preceding digit.
   • For left bracket '[': This denotes the start of a new repeat sequence. We might need to remember the current context (current string and current multiplier) by pushing them onto a stack.
   • For right bracket ']': This denotes the end of a repeat sequence. Here, we pop the top of the stack to get our last context, repeat the string encoding within the brackets as specified by the preceding number, and then continue building our string.
3. Continuously building and updating the resultant string based on the operations connected with each encountered character.
4. By the time we reach the end of the string, the stack should be back to its initial state, and we will have our fully decoded string ready to return.

This method efficiently manages the nested nature of the encoding and can straightforwardly handle even complex nested encoded patterns, as illustrated by the example inputs provided. The constraints ensure the procedure executes swiftly within acceptable limits, making this a robust solution for all provided test cases.

Solutions

class Solution {
public:
    string unrollString(string str) {
        int pos = 0;
        return helper(str, pos);
    }
    string helper(const string& str, int& pos) {
        string rebuilt;
        while (pos < str.length() && str[pos] != ']') {
            if (!isdigit(str[pos]))
                rebuilt += str[pos++];
            else {
                int num = 0;
                // calculate num while digit appears
                while (pos < str.length() && isdigit(str[pos]))
                    num = num * 10 + str[pos++] - '0';
                // skip '[' character
                pos++;
                string inner = helper(str, pos);
                // skip ']' character
                pos++;
                while (num-- > 0)
                    rebuilt += inner;
            }
        }
        return rebuilt;
    }
};