leetcode394. Decode String

题目要求

Given an encoded string, return it's 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].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

将一个字符串解码，要求按照次数展开原字符串中的中括号。如 3[a]2[bc] 对应的字符串就是 aaabcbc ，即a展开3次，bc展开2次。注意，源字符串中的括号是允许嵌套的，且展开的字符中不会包含任何数字。

思路一：递归

其实递归的思路是很明显的，一旦我们遇到一个左括号，我们就可以找到其对应的右括号，然后对括号中的内容递归的展开，再将返回结果给上层，根据上次的次数再次展开。

如 3[a2[c]] => 3[acc] => accaccacc 。

递归这里需要注意的是如何找到当前括号对应的右括号。这里可以采用一个小技巧，即从当前括号位置开始，每遇到一个左括号计数就+1，遇到一个右括号计数就-1，当计数器第一次被减为0时，则该位置上的右括号就是我们所要找的对应的右括号。

代码如下：

public String decodeString2(String s) {
        if (s.length() == 0)
            return "";

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                // 解析次数
                int digitStart = i++;
                while (s.charAt(i) >= '0' && s.charAt(i) <= '9')
                    i++;
                int num = Integer.parseInt(s.substring(digitStart, i));

                // 找到对应的右括号
                int strStart = i+1; // number must be followed by '['
                int count = 1; 
                i++;
                while (count != 0) {
                    if (s.charAt(i) == '[')
                        count++;
                    else if (s.charAt(i) == ']')
                        count--;
                    i++;
                }
                i--; 

                // 取子字符串
                String subStr = s.substring(strStart, i);

                // 将子字符串解码
                String decodeStr = decodeString(subStr);

                // 将解码的结果拼接到当前的字符串后面
                for (int j = 0; j < num; j++) {
                    sb.append(decodeStr);
                }

            } else {
                // 添加首元素
                sb.append(c);
            }

        }

        return sb.toString();
    }

思路二：栈

我们知道，有一些递归的思路是可以转化为栈的，这里同样如此。利用栈我们可以存储外围层已持有的字符串以及应当展开的次数。用栈的思路来写要求思路更加严谨，以免出现逻辑错误。首先，我们会用两个指针lft，rgt分别来记录数字的起始位置和结束位置。同时，rgt还作为我们遍历整个字符串的指针。rgt的情形有如下几种可能：

1. rgt指向[
2. rgt指向]
3. rgt指向数字
4. rgt指向字母

下面我们来逐个分析各种场景：

1. rgt指向[

此时左括号的左侧只会有一种情形，它的左边一定是数字。

因此当我们遇到左括号时，我们应当记录左括号左边的数字，并将lft指针移动到左括号下一个位置。这里需要额外注意的是，如果当前该括号外围存在父元素，则我们应当将父元素的计数和已有字符串压入栈中。可以将这个操作理解为上下文切换。

2. rgt指向]

右括号意味着当前的字符展开序列遍历完毕，因此我们需要做以下几件事情：

1. 将lft和rgt之间的内容append到当前上下文的字符串中
2. 根据展开次数展开当前上下文的字符串
3. 如果存在父元素，则从栈中弹出父元素，恢复父级上下文
4. 将当前上文得到的结果append到父元素的字符串中

3. rgt指向字母

我们需要将rgt指向的字母添加到当前的上下文字符串中去。不要忘记将左指针移动到当前位置后面

4. rgt指向数字

数字将会在遇见 [ 时提取出来，因此我们无需进行任何处理

一个具体的例子

假如现在输入的字符串为 3[a2[c]] ，我们有字符串栈s，计数栈c，指针lft，rgt，并用临时变量tmp，number分别记录当前上下文中计数和字符串。运行情况如下：

lft=0 rgt=0 : 不执行任何操作
lft=0 rgt=1 : 解析当前上下文应当展开的次数 number=3, lft=2
lft=2 rgt=2 : 将当前的字符添加到当前的上下文中去，tmp="a" lft=3
lft=3 rgt=3 : 不做任何处理
lft=3 rgt=4 : 将父级上下文压入栈中，并解析当前上下文的展开次数 s:["a"] c:[3] lft=5 tmp="" number=2
lft=5 rgt=5 : 将当前的字符添加到当前的上下文中去，tmp="c" lft=6
lft=6 rgt=6 : 展开当前字符串，并恢复父级上下文, tmp="a"+"cc", number=3 s:[] c:[] lft=7
lft=7 rgt=7 : 展开当前字符串，= 此时没有父级上下文，因此无需恢复。tmp="accaccacc" number=0

代码如下：

public String decodeString(String s) {
        Stack<Integer> count = new Stack<>();
        Stack<StringBuilder> letters = new Stack<>();
        int lft = 0, rgt = -1;
        int number = 0;
        StringBuilder result = null;
        while(++rgt < s.length()) {
            char c = s.charAt(rgt);
            if(c == '[') {
                if(result != null) {
                    count.push(number);
                    letters.push(result);
                }
                result = new StringBuilder();
                number = Integer.valueOf(s.substring(lft, rgt));
                lft = rgt+1;
            }else if(c == ']') {
                result.append(s.substring(lft, rgt));                    
                StringBuilder tmp = new StringBuilder(result);
                for(int i = 0 ; i<number-1 ; i++) {
                    result.append(tmp);
                }
                if(!letters.isEmpty()) {
                    StringBuilder pop = letters.pop();
                    pop.append(result);
                    result = pop;
                    number = count.pop();
                }
                lft = rgt+1;
            }else if(Character.isAlphabetic(c)) {
                if(result==null) {
                    result = new StringBuilder();
                }
                result.append(c);
                lft = rgt+1;
            }
        }
        if(result == null) {
            result = new StringBuilder();
        }
        result.append(s.substring(lft, rgt));
        return result.toString();
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~