Decode String

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;
    }
};

This solution in C++ deals with decoding a string where certain parts of the string are enclosed in brackets [] with a number prefix. The number indicates how many times the string within the brackets should be repeated. The input to the function unrollString is a string that you want to decode, and it returns the decoded string.

• The unrollString function initializes the position and calls the helper function helper.
• Inside the helper function, an empty string rebuilt is initialized to start constructing the decoded version of the sub-part of the string it currently processes.

The process unfolds as follows:

1. Iterate character by character in the str array until you encounter a closing bracket ] or exhaust the string.
2. If the current character is not a digit, simply append it to rebuilt.
3. If the character is a digit, compute the full number that represents how many times the subsequent string pattern should repeat.
4. After computing the repetition number, ignore the open bracket [ and recursively invoke helper to process the string enclosed within the brackets.
5. After getting the decoded string from the recursive call, skip the closing bracket ].
6. Append the decoded string to rebuilt as many times as specified by the number calculated earlier.

The recursion effectively handles nested patterns by processing innermost strings first, gradually working outwards, accurately maintaining the sequence and the number of repetitions necessary at each level. The function finally returns the fully decoded string once all nested patterns have been processed.

This methodology is space-efficient as it utilizes a reference to the position and string constructs to decode segments without duplicating arrays or strings unnecessarily.

class Solution {
    int position = 0;
    String decode(String str) {
        StringBuilder output = new StringBuilder();
        while (position < str.length() && str.charAt(position) != ']') {
            if (!Character.isDigit(str.charAt(position)))
                output.append(str.charAt(position++));
            else {
                int multiplier = 0;
                while (position < str.length() && Character.isDigit(str.charAt(position)))
                    multiplier = multiplier * 10 + str.charAt(position++) - '0';
                position++; // Skip the '['
                String innerDecoded = decode(str);
                position++; // Skip the ']'
                while (multiplier-- > 0)
                    output.append(innerDecoded);
            }
        }
        return output.toString();
    }
}

The Java program provided offers a solution for decoding a specially formatted string that includes numbers followed by square brackets. These numbers determine how many times the sequence inside the brackets should be repeated. Below is a summary of how the code solves this problem and how each part of the code contributes to the solution:

• Class and Method Structure: A class named Solution includes a method called decode which takes a string str as input and uses a recursive approach to decode it.

• Variables: There is one instance variable position used to keep track of the current index in the input string during decoding.

• Main Decoding Loop:

  • Non-Digit Characters: Directly appends any character, that is not a digit, to a StringBuilder named output.
  • Digit Handling: When a digit is encountered, it calculates the entire number (which might be multi-digit) and this represents the multiplier indicating the number of times to repeat the string inside the subsequent square brackets.
  • Recursive Decoding:
    • Skips the opening bracket '[' by incrementing position.
    • Calls itself recursively to decode the string inside the brackets. This ensures nested patterns are decoded correctly.
    • After the closing bracket ']', the decoded string from the recursive call is appended to output as many times as specified by the multiplier.

• Termination Condition: The main decoding loop continues until position reaches the end of the string or encounters a closing bracket ], which helps in managing nested structures.

• Returning the Result: Once the loop completes, the method returns the fully decoded string built in the output.

This solution efficiently handles nested and multi-layered encoded strings using recursion. Each recursive call processes another level of encoding, allowing the method to handle complex patterns like 3[a2[c]] intuitively, by resolving 2[c] first then repeating the resolved string as specified.