394. Decode String – Leetcode Solutions

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"

class Solution:
    def decodeString(self, s: str) -> str:
        # Stack to hold (current string, repetition count)
        stack = []
        # Current working string
        current_string = ""
        # Current repetition count
        current_number = 0

        for char in s:
            if char.isdigit():
                # Build the current number (handles multi-digit numbers)
                current_number = current_number * 10 + int(char)
            elif char == '[':
                # Push the current string and number to the stack
                stack.append((current_string, current_number))
                # Reset current string and number for the next scope
                current_string = ""
                current_number = 0
            elif char == ']':
                # Pop from the stack, repeat the current string, and append to previous string
                prev_string, repeat_count = stack.pop()
                current_string = prev_string + (current_string * repeat_count)
            else:
                # Append the current character to the working string
                current_string += char

        return current_string

class Solution {
public:
    string decodeString(string s) {
        // Stack to store previous string states and repeat counts
        stack<string> strStack;
        stack<int> countStack;
        
        // Current decoded string
        string currentStr = "";
        
        // Variable to hold the current multiplier value
        int currentNum = 0;

        // Iterate over the input string character by character
        for (char c : s) {
            if (isdigit(c)) {
                // Build the current multiplier (k)
                currentNum = currentNum * 10 + (c - '0');
            } else if (c == '[') {
                // Push the current state into stacks and reset
                countStack.push(currentNum);
                strStack.push(currentStr);

                // Reset current state
                currentNum = 0;
                currentStr = "";
            } else if (c == ']') {
                // Pop the last state from stacks
                int repeatCount = countStack.top(); countStack.pop();
                string prevStr = strStack.top(); strStack.pop();

                // Append the repeated string to the previous string
                string decoded = "";
                for (int i = 0; i < repeatCount; ++i) {
                    decoded += currentStr;
                }

                // Update current string with the combined result
                currentStr = prevStr + decoded;
            } else {
                // Append regular characters to the current string
                currentStr += c;
            }
        }

        // Return the fully decoded string
        return currentStr;
    }
};

var decodeString = function(s) {
    // Initialize a stack to hold characters and numbers during processing.
    let stack = [];
    
    // Iterate through each character in the string.
    for (let char of s) {
        if (char !== ']') {
            // If the character is not a closing bracket, push it onto the stack.
            stack.push(char);
        } else {
            // If the character is a closing bracket, process the stack to decode the segment.

            // Step 1: Build the encoded substring inside the brackets.
            let substring = '';
            while (stack.length && stack[stack.length - 1] !== '[') {
                substring = stack.pop() + substring;
            }
            
            // Remove the opening bracket '['.
            stack.pop();

            // Step 2: Get the number (k) associated with this substring.
            let k = '';
            while (stack.length && /\d/.test(stack[stack.length - 1])) {
                k = stack.pop() + k;
            }
            k = parseInt(k);

            // Step 3: Expand the substring k times and push it back onto the stack.
            stack.push(substring.repeat(k));
        }
    }

    // Join the stack to form the final decoded string.
    return stack.join('');
};

class Solution {
    public String decodeString(String s) {
        // Stack to hold the count of repetitions for each nested segment
        Stack<Integer> countStack = new Stack<>();
        // Stack to hold the result of previous segments
        Stack<StringBuilder> resultStack = new Stack<>();
        // StringBuilder to construct the current segment
        StringBuilder current = new StringBuilder();
        int k = 0; // To track the current multiplier
        
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                // If the character is a digit, update the multiplier (k)
                k = k * 10 + (ch - '0');
            } else if (ch == '[') {
                // Push the multiplier and current segment to their respective stacks
                countStack.push(k);
                resultStack.push(current);
                // Reset for the next segment
                k = 0;
                current = new StringBuilder();
            } else if (ch == ']') {
                // End of the current nested segment
                // Pop the multiplier and the previous segment from the stacks
                int repeatCount = countStack.pop();
                StringBuilder previous = resultStack.pop();
                // Repeat the current segment and append it to the previous segment
                for (int i = 0; i < repeatCount; i++) {
                    previous.append(current);
                }
                // Update the current segment with the combined result
                current = previous;
            } else {
                // Append regular characters to the current segment
                current.append(ch);
            }
        }
        // Return the final decoded string
        return current.toString();
    }
}