394. Decode String

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10⁵.

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].



        
        
            Solution
            
            
            
                Python Solution
                class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        curr_str = ''
        curr_num = 0
        
        for c in s:
            if c.isdigit():
                curr_num = curr_num * 10 + int(c)
            elif c == '[':
                stack.append((curr_str, curr_num))
                curr_str = ''
                curr_num = 0
            elif c == ']':
                prev_str, num = stack.pop()
                curr_str = prev_str + num * curr_str
            else:
                curr_str += c
        
        return curr_str
                
                
                    Time Complexity: O(maxK * n)
                    Where maxK is the maximum value of k and n is the length of the input string.
                    
                    Space Complexity: O(m)
                    Where m is the number of nested brackets.
                
            

            
            
                Java Solution
                class Solution {
    public String decodeString(String s) {
        Stack strStack = new Stack<>();
        Stack countStack = new Stack<>();
        StringBuilder currStr = new StringBuilder();
        int currNum = 0;
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                currNum = currNum * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(currNum);
                strStack.push(currStr);
                currStr = new StringBuilder();
                currNum = 0;
            } else if (c == ']') {
                StringBuilder temp = currStr;
                currStr = strStack.pop();
                int repeatTimes = countStack.pop();
                
                while (repeatTimes-- > 0) {
                    currStr.append(temp);
                }
            } else {
                currStr.append(c);
            }
        }
        
        return currStr.toString();
    }
}
                
                
                    Time Complexity: O(maxK * n)
                    Where maxK is the maximum value of k and n is the length of the input string.
                    
                    Space Complexity: O(m)
                    Where m is the number of nested brackets.
                
            

            
            
                C++ Solution
                class Solution {
public:
    string decodeString(string s) {
        stack> st;
        string currStr;
        int currNum = 0;
        
        for (char c : s) {
            if (isdigit(c)) {
                currNum = currNum * 10 + (c - '0');
            } else if (c == '[') {
                st.push({currStr, currNum});
                currStr = "";
                currNum = 0;
            } else if (c == ']') {
                auto [prevStr, num] = st.top();
                st.pop();
                string temp = currStr;
                currStr = prevStr;
                
                while (num--) {
                    currStr += temp;
                }
            } else {
                currStr += c;
            }
        }
        
        return currStr;
    }
};
                
                
                    Time Complexity: O(maxK * n)
                    Where maxK is the maximum value of k and n is the length of the input string.
                    
                    Space Complexity: O(m)
                    Where m is the number of nested brackets.
                
            

            
            
                JavaScript Solution
                /**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    const stack = [];
    let currStr = '';
    let currNum = 0;
    
    for (let c of s) {
        if (!isNaN(c)) {
            currNum = currNum * 10 + parseInt(c);
        } else if (c === '[') {
            stack.push([currStr, currNum]);
            currStr = '';
            currNum = 0;
        } else if (c === ']') {
            const [prevStr, num] = stack.pop();
            currStr = prevStr + currStr.repeat(num);
        } else {
            currStr += c;
        }
    }
    
    return currStr;
};
                
                
                    Time Complexity: O(maxK * n)
                    Where maxK is the maximum value of k and n is the length of the input string.
                    
                    Space Complexity: O(m)
                    Where m is the number of nested brackets.
                
            

            
            
                C# Solution
                public class Solution {
    public string DecodeString(string s) {
        Stack<(string str, int count)> stack = new Stack<(string, int)>();
        StringBuilder currStr = new StringBuilder();
        int currNum = 0;
        
        foreach (char c in s) {
            if (char.IsDigit(c)) {
                currNum = currNum * 10 + (c - '0');
            } else if (c == '[') {
                stack.Push((currStr.ToString(), currNum));
                currStr.Clear();
                currNum = 0;
            } else if (c == ']') {
                var (prevStr, num) = stack.Pop();
                string temp = currStr.ToString();
                currStr = new StringBuilder(prevStr);
                
                while (num-- > 0) {
                    currStr.Append(temp);
                }
            } else {
                currStr.Append(c);
            }
        }
        
        return currStr.ToString();
    }
}
                
                
                    Time Complexity: O(maxK * n)
                    Where maxK is the maximum value of k and n is the length of the input string.
                    
                    Space Complexity: O(m)
                    Where m is the number of nested brackets.
                
            
        

        
        
            Approach Explanation
            
            
                
                    The solution uses a stack-based approach to handle nested brackets:
                
                
                
                    Key Insights:
                        
                            Stack usage
                            String building
                            Number parsing
                            Nested structure
                        
                    
                    Algorithm Steps:
                        
                            Parse numbers
                            Handle brackets
                            Build strings
                            Manage nesting
                        
                    
                

                
                    Implementation Details:
                    

                        Stack operations
                        String concatenation
                        Number tracking
                        Bracket matching
                    
                

                
                    Optimization Insights:
                    

                        StringBuilder usage
                        Efficient parsing
                        Memory management
                        Stack efficiency
                    
                

                
                    Edge Cases:
                    

                        Empty string
                        Single character
                        Multiple digits
                        Nested brackets