LeetCode 394: Decode String Solution

Master LeetCode problem 394 (Decode String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

394. Decode String

Medium

String Stack Recursion

Problem Explanation

Explanation

To decode the given encoded string, we can use a stack to keep track of the characters and numbers we encounter. We iterate through the input string character by character and handle the following cases:

If we encounter a digit, we update the current number being built.
If we encounter an opening bracket, we push the current number and decoded string so far onto the stack and reset them.
If we encounter a closing bracket, we pop the number and decoded string from the stack, repeat the decoded string the required number of times, and append it to the decoded string built so far.
If we encounter a letter, we simply append it to the decoded string.

Finally, the stack will contain the decoded string of the input string.

Time Complexity: O(maxK * n), where n is the length of the input string and maxK is the maximum value of k in the input string.

Space Complexity: O(n), where n is the length of the input string.

Solution Code

class Solution {
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        StringBuilder currentStr = new StringBuilder();
        int currentNum = 0;

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                currentNum = currentNum * 10 + (c - '0');
            } else if (c == '[') {
                numStack.push(currentNum);
                strStack.push(currentStr.toString());
                currentNum = 0;
                currentStr = new StringBuilder();
            } else if (c == ']') {
                int num = numStack.pop();
                StringBuilder tmp = new StringBuilder();
                for (int i = 0; i < num; i++) {
                    tmp.append(currentStr);
                }
                currentStr = new StringBuilder(strStack.pop() + tmp.toString());
            } else {
                currentStr.append(c);
            }
        }

        return currentStr.toString();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 394 (Decode String)?

This page provides optimized solutions for LeetCode problem 394 (Decode String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 394 (Decode String)?

The time complexity for LeetCode 394 (Decode String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 394 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 394 in Java, C++, or Python.

Back to LeetCode Solutions