Google – Decompress String

Google – Decompress String
给一个string，比如abbaba4x[a]bb3x[abaa2x[bab]]。 4x[a]就表示aaaa, 2x[bab]就表示有两个连续的bab，babbab. 要求decompress 这个string。
[Solution]
[Solution #1]
recursion
碰到[]就递归整个括号里的东西，不管里面是否还有嵌套，也不管有几层嵌套。把递归回来的string整个append到stringbuilder，然后继续后面的。在碰到'['时需要找到与之对应的']'，而不是在那之后的第一个close bracket！
[Solution #2]
Iterative
用一个stack来记录所有的Character, 一旦碰到close bracket ], 从stack里pop直到pop出open bracket。这样可以保证这两个括号肯定是一对并且在最里层。decompress之后把得到的结果再push回stack。继续后面的。

// recursive

class Solution {

  public String decompression(String s) {

    if (s == null || s.isEmpty()) {

      return s;

    }

 

    StringBuilder result = new StringBuilder();

 

    for (int i = 0; i < s.length(); i++) {

      char c = s.charAt(i);

      if (c >= 'a' && c <= 'z') {

        result.append(c);

      }

      else if (c >= '1' && c <= '9') {

        StringBuilder tmp = new StringBuilder();

        int xIdx = s.indexOf("x", i);

        int cnt = Integer.parseInt(s.substring(i, xIdx));

        i = xIdx + 2;

        int openLeft = 1;

        while (true) {

          if (s.charAt(i) == ']') {

            openLeft--;

            if (openLeft == 0) {

              break;

            }

            else {

              tmp.append(s.charAt(i));

            }

          }

          else if (s.charAt(i) == '[') {

            openLeft++;

            tmp.append(s.charAt(i));

          }

          else {

            tmp.append(s.charAt(i));

          }

          i++;

        }

 

        String sub = decompression(tmp.toString());

        for (int k = 0; k < cnt; k++) {

          result.append(sub);

        }

      }

    }

 

    return result.toString();

  }

}

// iterative stack

class Solution2 {

  public String decompression(String s) {

    if (s == null || s.isEmpty()) {

      return s;

    }

 

    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {

      if (c != ']') {

        stack.push(c);

      }

      else {

        List<Character> pattern = new LinkedList<>();

        while (true) {

          char top = stack.pop();

          if (top == '[') {

            break;

          }

          else {

            pattern.add(0, top);

          }

        }

        stack.pop();

        StringBuilder tmp = new StringBuilder();

        while (stack.peek() >= '0' && stack.peek() <= '9') {

          tmp.insert(0, stack.pop());

        }

        int cnt = Integer.parseInt(tmp.toString());

 

        for (int i = 0; i < cnt; i++) {

          for (char p : pattern) {

            stack.push(p);

          }

        }

      }

    }

 

    StringBuilder result = new StringBuilder();

    while (!stack.isEmpty()) {

      result.append(stack.pop());

    }

 

    return result.reverse().toString();

  }

}

Read full article from Google – Decompress String