algoadvance

Leetcode 394. Decode String

Problem Statement:

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; No extra white spaces, square brackets are well-formed, etc.

Examples:

Clarifying Questions:

  1. Are the encoded strings always well-formed, i.e., every ‘[’ has a matching ‘]’ and the numbers are valid positive integers?
    • Assumption: Yes, the input is always valid.
  2. Can the input string contain nested encoded strings?
    • Assumption: Yes, such as in the second example.
  3. Is it necessary to handle edge cases like an empty string?
    • Assumption: Yes, but it’s straightforward since an empty string should return an empty result.

Strategy:

  1. Use two stacks to keep track of numbers and the corresponding strings being decoded.
  2. Traverse the string character by character:
    • If a digit is encountered, build the full number.
    • If an opening bracket ‘[’ is encountered, push the current number and current decoded string onto their respective stacks and reset them.
    • If a closing bracket ‘]’ is encountered, pop from both stacks, multiply the current decoded string the appropriate number of times, and append it to the last decoded string from the stack.
    • If a letter is encountered, append it to the current decoded string.
  3. At the end of the traversal, the decoded string will be built correctly.

Code:

import java.util.Stack;

public class DecodeString {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;
        
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                k = k * 10 + (ch - '0');
            } else if (ch == '[') {
                countStack.push(k);
                stringStack.push(currentString.toString());
                currentString = new StringBuilder();
                k = 0; // reset k for new number
            } else if (ch == ']') {
                StringBuilder decodedString = new StringBuilder(stringStack.pop());
                int repeatTimes = countStack.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    decodedString.append(currentString);
                }
                currentString = decodedString;
            } else {
                currentString.append(ch);
            }
        }
        
        return currentString.toString();
    }

    public static void main(String[] args) {
        DecodeString solution = new DecodeString();
        System.out.println(solution.decodeString("3[a]2[bc]")); // "aaabcbc"
        System.out.println(solution.decodeString("3[a2[c]]")); // "accaccacc"
        System.out.println(solution.decodeString("2[abc]3[cd]ef")); // "abcabccdcdcdef"
    }
}

Time Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI