How to use Go Java algorithm for string decoding?

String Decoding

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], which means that the encoded_string inside the square brackets is repeated k times. Note that k is guaranteed to be a positive integer.

You can assume that the input string is always valid; there are no extra spaces in the input string, and the input square brackets always meet the format requirements.

In addition, you can think that the original data does not contain numbers. All numbers only represent the number of repetitions k. For example, there will be no input like 3a or 2[4].

• 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"

Method 1: Stack (Java)

See When it comes to bracket matching, the first thing you should think of is using the stack to solve the problem.

First of all, because the number may have more than one digit, two stacks can be used for clarity and convenience, one to store numbers and one to store characters. When a character other than ] is encountered, it is first put into the character stack. When a number is encountered, the complete number is converted and put into the number stack. When ] is encountered, the characters up to [ are popped out of the character stack to form a temporary string and popped out. The top element of the number stack, repeat the temporary string the number of times and then put it back into the character stack.

When the original string is traversed from left to right, the element in the stack is the final answer

Specific method idea: Traverse the stack

• If the current The character is a digit, parse out a number (multiple consecutive digits) and push it onto the stack

• If the current character is a letter or left bracket, push it directly onto the stack

• If the current character is a right bracket, start popping it from the stack until the left bracket pops. The popping sequence is reversed and spliced ​​into a string. At this time, the number on the top of the stack is taken out, and this string should appear. times, we construct a new string based on this number and the string and push it onto the stack

class Solution {
    int ptr;
    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;
        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == &#39;[&#39;) {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++)));
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }
        return getString(stk);
    }
    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }
    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}

Time complexity: O(N)

Space complexity: O (N)

Method 2: Recursion (Go)

The method mentioned above uses the stack, so we can then think of using recursion to complete it. For specific recursive ideas, please see below.

Need to solve the nesting problem between multiple brackets. That is, overlapping subproblems. You can use stack or recursion to solve problems.

• 1. First identify the position where the right bracket ends.

• 2. When a left bracket is encountered, i 1 is passed to the next time

• 3. End the operation of the left bracket and set the number of products to zero. i=the position where the right bracket last touched. Continue adding the remaining characters outside the right bracket.

Specific idea: parse the string from left to right:

• If the current position is a digit, then it must contain a square bracket after This is the case for the string represented by: k[...]:

• We can parse out a number first, then parse the left bracket, and recursively parse the following Content, it will be returned when it encounters the corresponding right bracket. At this time, we can construct a new string X * s′

## based on the parsed number x and the parsed string s' in the brackets.
• #After we parse k[...], we call the recursive function again to parse the content on the right side of the right bracket

• If the current position is a letter bit, then we parse it directly The current letter, and then recursively parse down the content after this letter.

func decodeString(s string) string {
    var decode func(start int) (string, int)
    decode = func(start int) (str string, end int) {
        num:= 0
        for i := start; i < len(s); i++ {
            if isNumber(s[i]) {
                num = num*10 + int(s[i]-&#39;0&#39;)
            } else if isLetter(s[i]) {
                str += string(s[i])
            } else if s[i] == &#39;[&#39; {
                item, index := decode(i + 1)
                for num != 0 {
                    str += item
                    num--
                }
                i = index
            } else if s[i] == &#39;]&#39; {
                end = i
                break
            }
        }
        return str, end
    }
    res, _ := decode(0)
    return res
}
func isLetter(u uint8) bool {
    return u >= &#39;A&#39; && u <= &#39;Z&#39; || u >= &#39;a&#39; && u <= &#39;z&#39;
}
func isNumber(u uint8) bool {
    return u >= &#39;0&#39; && u <= &#39;9&#39;
}

Time complexity: O(N)
Space complexity: O(N)

The above is the detailed content of How to use Go Java algorithm for string decoding?. For more information, please follow other related articles on the PHP Chinese website!