LeetCode_ Stack_ Difficulties_ 394. string decoding

1. subject

Given an encoded string , Returns the decoded string .

The coding rule is : k[encoded_string], Represents the encoded_string Just repeat k Time . Be careful k Positive integer guaranteed .

You can think that the input string is always valid ; There are no extra spaces in the input string , And the square brackets entered always meet the format requirements .

Besides , You can assume that the raw data does not contain numbers , All numbers only indicate the number of repetitions k , For example, there is no such thing as 3a or 2[4] The input of .

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”

Example 4：
Input ：s = “abc3[cd]xyz”
Output ：“abccdcdcdxyz”

Tips ：
1 <= s.length <= 30
s By lowercase letters 、 Numbers and square brackets ‘[]’ form
s Guarantee is a It works The input of .
s The value range of all integers in is [1, 300]

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/decode-string

2. Ideas

（1） Stack
Train of thought reference Official solution to this problem .

3. Code implementation （Java）

// Ideas 1———— Stack 
public class Solution {
    
    int index = 0;
    
    public String decodeString(String s) {
    
        // Use linked list to simulate stack 
        LinkedList<String> stack = new LinkedList<String>();
        index = 0;
        while (index < s.length()) {
    
            char cur = s.charAt(index);
            if (Character.isDigit(cur)) {
    
                // Get a number  k  Parallel stack (1 ≤ k ≤ 300)
                String digits = getDigits(s);
                stack.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
    
                // Get a letter and put it on the stack 
                stack.addLast(String.valueOf(s.charAt(index++)));
            } else {
    
                index++;
                LinkedList<String> sub = new LinkedList<>();
                while (!"[".equals(stack.peekLast())) {
    
                    sub.addLast(stack.removeLast());
                }
                Collections.reverse(sub);
                // Left bracket out of stack 
                stack.removeLast();
                // At this time, the stack top element is the current  sub  The number of times the corresponding string should appear 
                int times = Integer.parseInt(stack.removeLast());
                StringBuffer buffer = new StringBuffer();
                String str = getString(sub);
                // Construct string 
                while (times > 0) {
    
                    buffer.append(str);
                    times--;
                }
                // Add the constructed string to the stack 
                stack.addLast(buffer.toString());
            }
        }
        return getString(stack);
    }
    
    public String getDigits(String s) {
    
        StringBuffer buffer = new StringBuffer();
        while (Character.isDigit(s.charAt(index))) {
    
            buffer.append(s.charAt(index++));
        }
        return buffer.toString();
    }
    
    // Splicing  stack  And returns 
    public String getString(LinkedList<String> stack) {
    
        StringBuffer buffer = new StringBuffer();
        for (String s : stack) {
    
            buffer.append(s);
        }
        return buffer.toString();
    }
}