Basic algorithm class day04

leetcode394 string decoding


This problem is intuitively associated with stack processing. My idea is:
Traverse the string and stack it from left to right. If you can merge, merge it first and then add it to the stack
For example, 232[asc]33[ass]
First, put 232, asc, 33, ass into a string and add it to the stack
When you encounter a right bracket, you start to pop it out. As for how many elements to pop, judge whether the top of the stack is a left bracket or not

If the top of the current stack is left bracket, we need to pop up the stack twice, take out the number that needs to be increased by several times. The code is relatively simple and should be understood very well

public static String decodeString(String s) {
        String res = "";
        Stack<String> stack = new Stack<>();//Use stack to store data
        for (int i = 0; i < s.length(); i++) {
            String middle = s.substring(i, i + 1);//It doesn't use bytes, because it's troublesome to use bytes to judge if the number is 97
            if (middle.matches("[0-9]")) { //Regular expression matching, first determine whether the current is a number
                String num = middle;
                while (i + 1 < s.length() && s.substring(i + 1, i + 2).matches("[0-9]")) {//Judge whether it is a continuous number
                    num += s.substring(i + 1, i + 2);
                    i++;
                }
                stack.add(num);//Add this number to the stack

            } else if (middle.matches("[a-z]") || middle.equals("[") || middle.matches("[A-Z]")) {//Using regular expressions to judge letters
                if (middle.equals("["))
                    stack.add(middle);
                else {
                    String ele = middle;
                    while (i + 1 < s.length() && s.substring(i + 1, i + 2).matches("[a-z]") ||
                            i + 1 < s.length() && s.substring(i + 1, i + 2).matches("[A-Z]")) {//Judge if it's a continuous letter
                        ele += s.substring(i + 1, i + 2);
                        i++;
                    }
                    stack.add(ele);//Add this string to the stack
                }

            } else if (middle.equals("]")) {//The right bracket is encountered and starts to pop out
                String temp = "";//Intermediate variable
                while (!stack.peek().equals("["))//Pop up the next left bracket before it to make string splicing
                    temp = stack.pop()+temp;
                stack.pop();//This is the left bracket
                int count = Integer.parseInt(stack.pop());//This is a number
                String mid = temp;
                for (int j = 0; j < count - 1; j++) {//This step is to repeat the string the number of times
                    temp += mid;
                }
                stack.add(temp);//Put it back in the stack

            }
        }
        while (!stack.empty()) { //Finally, we'll dump the stack
            String middle2 = "";
            middle2 = stack.pop() + middle2;
            res = middle2 + res;
        }

        return res;
    }

Posted on Thu, 04 Jun 2020 08:53:08 -0700 by mrneilrobinson