Decode String - Java Solution

1. Introduction

This post explores a solution to the "Decode String" problem, which involves unrolling a compressed string according to specific encoding rules. The encoding format is k[encoded_string], indicating that the encoded_string needs to be repeated k times. This problem is a good example of stack usage in string manipulation.

Problem

Given an encoded string, the goal is to return its decoded string. The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is repeated k times. The input string is always valid and does not contain any digits outside the encoding format.

2. Solution Steps

1. Use two stacks: one for counts and another for the partial decoded strings.

2. Iterate through the string character by character.

3. If the character is a digit, compute the full number and push it onto the counts stack.

4. If the character is '[', push the current decoded string onto the stack and reset it.

5. If the character is ']', pop from both stacks and append the decoded string k times as specified by the count stack.

6. If the character is a letter, append it to the current decoded string.

7. Continue the process until the entire string is decoded.

3. Code Program

import java.util.Stack;

public class DecodeString {
    public static void main(String[] args) {
        String s = "3[a2[c]]";
        System.out.println(decodeString(s)); // Test the function
    }

    // Function to decode the string
    public static String decodeString(String s) {
        Stack<Integer> counts = new Stack<>();
        Stack<String> resultStack = new Stack<>();
        String result = "";
        int index = 0;

        while (index < s.length()) {
            if (Character.isDigit(s.charAt(index))) {
                int count = 0;
                while (Character.isDigit(s.charAt(index))) {
                    count = 10 * count + (s.charAt(index) - '0');
                    index++;
                }
                counts.push(count);
            } else if (s.charAt(index) == '[') {
                resultStack.push(result);
                result = "";
                index++;
            } else if (s.charAt(index) == ']') {
                StringBuilder temp = new StringBuilder(resultStack.pop());
                int repeatTimes = counts.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    temp.append(result);
                }
                result = temp.toString();
                index++;
            } else {
                result += s.charAt(index);
                index++;
            }
        }

        return result;
    }
}

Output:

"accaccacc"

Explanation:

1. decodeString: This function decodes the encoded string.

2. Two stacks, counts and resultStack, are used to keep track of repeat counts and the current part of the decoded string, respectively.

3. The function iterates over each character in the string, handling digits, opening brackets ('['), closing brackets (']'), and letters.

4. When a digit is encountered, the entire number is computed and pushed onto the counts stack.

5. On encountering '[', the current result is pushed onto resultStack, and result is reset.

6. When ']' is encountered, the function pops from both stacks, repeating the result string as many times as the top value on the counts stack, and then concatenates it with the string popped from resultStack.

7. Letters are appended to the current result.

8. This approach efficiently decodes the string using stack operations, ensuring that nested encodings are handled correctly.