394. String decoding - auxiliary stack

One 、 Title Description

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"

Two 、 Problem solving

Auxiliary stack

Push the characters in the string onto the stack , If it's not the right bracket , Then press the characters on the stack , If you encounter the right bracket , Out of the stack , preservation [ ] Characters in parentheses , If you continue to stack, it is a number , Then save the number N, And then [ ] Copy N Time , Keep pressing the stack . Finally, the elements in the stack can be removed from the stack .

class Solution {
    
    public String decodeString(String s) {
    
        Stack<Character> stack = new Stack<>();
        for(char ch : s.toCharArray()){
    
            if(ch != ']'){
    
                // If it's not the right bracket   Just into the stack 
                stack.push(ch);
            }else{
    
                // If you encounter the left bracket   Out of the stack 
                // Remove [ ] String in 
                StringBuilder sb = new StringBuilder();
                // Judge whether the stack is empty   also   Whether the elements of the stack are characters 
                while(!stack.isEmpty() && Character.isLetter(stack.peek())){
    
                    sb.append(stack.pop());
                }
                // Flip the string 
                String substr = sb.reverse().toString();
                // Left parenthesis encountered , Then directly put the left bracket out of the stack 
                stack.pop();

                // Determine whether the string in the stack is a number 
                sb = new StringBuilder();
                while(!stack.isEmpty() && Character.isDigit(stack.peek())){
    
                    // If it's a number 
                    sb.append(stack.pop());
                }

                int cnt = Integer.valueOf(sb.reverse().toString());
                for(int i = 0;i<cnt;i++){
    
                    // Concatenate strings cnt Then press the stack 
                    for(char subch : substr.toCharArray()){
    
                        stack.push(subch);
                    }
                }

            }
        }

        // Remove the elements from the stack 
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()){
    
            res.append(stack.pop());
        }
        return res.reverse().toString();
    }
}

You can optimize , Use dual stack

class Solution {
    
    public String decodeString(String s) {
    
        StringBuilder sb = new StringBuilder();
        // Save string 
        Stack<StringBuilder> strstack = new Stack<>();
        // Save the numbers 
        Stack<Integer> numstack = new Stack<>();
        int sum = 0;
        for(char ch : s.toCharArray()){
    
            // Four situations  1、 If it's a number  2、 If it is a normal string  3、 If it's left parenthesis  4、 If it's right bracket 
            //1、 If it's a number 
            if(Character.isDigit(ch)){
    
                sum = sum * 10 + ch - '0';
            }else if(Character.isLetter(ch)){
    
                //2、 If it is a normal string  
                sb.append(ch);
            }else if(ch == '['){
    
                //3、 If it's left parenthesis 
                strstack.push(sb);
                numstack.push(sum);
                // to update 
                sb = new StringBuilder();
                sum = 0;
            }else{
    
                //4、 If it's right bracket 
                StringBuilder prestr = strstack.pop();
                int cnt = numstack.pop();
                for(int i = 0;i<cnt;i++){
    
                    prestr.append(sb);
                }
                sb = prestr;
            }
        }
        return sb.toString();
    }
}

other ：

class Solution {
    
    public String decodeString(String s) {
    
        // When you see the need for bracket matching, you should think of the stack 
        StringBuilder res=new StringBuilder();
        int num=0;
        // With the help of two stacks   Use the bucket stack to simulate it 
        LinkedList<String> character=new LinkedList<>();
        LinkedList<Integer> count=new LinkedList<>();
        for (char c:s.toCharArray()){
    
            // There are only four possibilities 
            if (c=='['){
    
                count.addLast(num);
                character.addLast(res.toString());
                // Empty, because I'll use it next time 
                num=0;
                res=new StringBuilder();
            }
            else if (c==']'){
    
                StringBuilder temp=new StringBuilder();
                int num1=count.removeLast();
                for (int i = 0; i < num1; i++) {
    
                    temp.append(res.toString());

                }
                res=new StringBuilder(character.removeLast()+temp);
            }
            else if(c<='9'&&c>='0'){
    
                num = num * 10 + c-'0';
            }else{
    
                res.append(c);
            }
        }
        return res.toString();
    }
}