Stacks and Queues

Java split()

• str.split(String regx, int limit)

  最多匹配limit-1次，返回的是以regx结尾的substring刨除regx部分，最多匹配limit-1次。如果limit是负数则匹配unlimited次。如果limit为0 则与str.split(String regx)相同，会去掉末尾的空字符串。 The array returned by this method contains each substring of this string that is terminated by another substring that matches the given expression or is terminated by the end of the string. The substrings in the array are in the order in which they occur in this string. If the expression does not match any part of the input then the resulting array has just one element, namely this string. If n is zero then the pattern will be applied as many times as possible, the array can have any length, and trailing empty strings will be discarded.

• str.split(String regx)

Java StringBuilder insert(int offset, char c)

    String s = "abcdef";
    char[] chars = s.toCharArray();
    StringBuilder sb = new StringBuilder();
    for (char aChar : chars) {
      //将字符插入到sb idx为0的位置
      sb.insert(0,aChar);
    }

    //outcome  fedcba

Leetcode 394. Decode String

Given an encoded string, return its decoded string.

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

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be 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”

• Solution
  1. 同 leetcode 71. Simplify Path 可以直到遇到‘[’再进行decoding，其他情况向stack中填入值
  2. 注意取出k值时有可能stack为空，要确认!empty()的情况下再进行取值操作

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ']'){
                //decoding
                List<Character> list = new ArrayList<>();
                while(stack.peek()!='[')
                    list.add(0, stack.pop());
                //remove '['
                stack.pop();
                int k = 0;
                int base = 1;
                while(!stack.isEmpty() && Character.isDigit(stack.peek())){
                    k = (stack.pop() - '0') * base + k;
                    base *= 10;
                }

                while(k > 0){
                    for(Character c : list)
                        stack.push(c);
                    k--;
                }
            }else{
                stack.push(s.charAt(i));
            }
        }

        char[] charArr = new char[stack.size()];
        for(int i = charArr.length - 1; i >= 0; i--)
            charArr[i] = stack.pop();
        
        return new String(charArr);
    }
}