力扣LeetCode 394题：字符串解码（栈，递归）-蒲公英云

题目：

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:
s = “3[a]2[bc]”, 返回 “aaabcbc”.
s = “3[a2[c]]”, 返回 “accaccacc”.
s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.

一、栈操作

因为有左右括号，中间字符需要重复多少次这样的情况，且给出的例子已经表明，这个题目显然存在括号嵌套。所以很容易想到需要用栈。

我们捋一捋思路，以第二个例子出发：

s = “ 3 [ a 2 [ c ] ] “

1.数字3，需要入栈；Stack=3
2.左括号，需要入栈；Stack=3[
3.字符a，需要入栈；Stack=3[a
4.数字2，需要入栈；Stack=3[a2
5.左括号，需要入栈；Stack=3[a2[
6.字符c，需要入栈；Stack=3[a2[c
1. 右括号，遇到右括号，则需要出栈。一直出到遇到左括号为止，这就是一个完整的括号里的需要重复的字符串内容了，结果是 c ；Stack=3[a2
  .继续出栈，这时候出来的一定是数字，代表这一段需要重复的次数。我们取出数字 2 ，将上一步取出的字符串进行重复得到 cc 。Stack=3[a
  将已经重复好的字符串再次入栈。因为只要没结束，就说明这一段是内嵌的，那么更外围的数字，重复的内容肯定包含里面的内容。Stack=3[acc
8.右括号，遇到右括号，出栈。出到遇到左括号为止，结果是acc；Stack=3
继续出栈，出来的是数字3，代表需要重复的次数。取出3重复字符串得到accaccacc；Stack=空
将已经重复好的字符串再次入栈。Stack=accaccacc
9.此时原字符串已经遍历完了，我们直接可以从栈里取出结果accaccacc。

总结一下步骤：

数字。解析完入栈。（这是因为数字可能出现多位数，因此应该解析出一个完整的数字之后再入栈）
左括号，入栈；
字符，入栈；
右括号，开始出栈，一直出到出来左括号。下一个出来的就是数字，用数字和出来的字符串进行重复之后，再入栈。（由于字符出来的是逆序，需要进行翻转）
继续遍历原字符串，重复以上过程。

以下是按照直接思路，用ArrayList模拟一个栈写出的代码。

class Solution {
    public String decodeString(String s) {
        StringBuilder ans=new StringBuilder();
        List<String> list=new ArrayList<>();
        int i=0;
        int count=0;
        //遍历整个s的操作
        while(i<s.length()){
            char c=s.charAt(i);
            //对于数字，先解析，再入栈
            if(c>='0'&&c<='9'){
                count=count*10+(c-'0');
                i++;
            }else if('['==c||c>='a' && c<='z' || c >='A' && c<='Z'){
                if(count!=0){
                    list.add(Integer.toString(count));
                    count=0;
                }
                list.add(String.valueOf(c));
                i++;
            }else{
                //(c==']'),初始化循环结果
                StringBuilder sb=new StringBuilder();
                //出栈准备
                int outPtr=list.size()-1;
                //直到出现前括号为止
                while(!(list.get(outPtr).equals("["))){
                    sb.insert(0,list.get(outPtr));
                    list.remove(outPtr);
                    outPtr--;
                }
                //此时的outPtr指向的是[,删除
                list.remove(outPtr--);
                //获取下一个，也就是数字
                int repeatNum=Integer.parseInt(list.get(outPtr));
                //然后数字也删除，并重新入栈
                list.remove(outPtr);
                for(int j=0;j<repeatNum;j++){
                    list.add(sb.toString());
                }
                i++;
            }
        }
        //当整个遍历完之后，重新存入list的就是一个完整的结果，只需要再读取出来就可以
        for(int j=0;j<list.size();j++){
            ans.append(list.get(j));
        }
        return ans.toString();
    }
}

其中，获取完整数字本来应该用while进行，但是不想破坏if-else语句。
观察到每一次出栈数字的下一个总是前括号，只需在遇到前括号的时候把count结果压入栈，同时再把count清零即可。

LeetCode评论里有用LinkedList，然后用了一些内部方法，会比这个更简洁一些。我自己的这个方法好处在于更偏向于顺序进行的过程。

以下是采用LinkedList的代码，同时用了两个栈保存数字和字符串。

class Solution {
    public String decodeString(String s) {
        StringBuilder ans = new StringBuilder();//结果
        int count = 0;
        //把字符和数字存入两个不同的栈
        LinkedList<Integer> countStack = new LinkedList<>();
        LinkedList<String> ansStack = new LinkedList<>();
        for(Character c : s.toCharArray()) {
            if(c >= '0' && c <= '9'){
                count = count * 10 + Integer.parseInt(c + "");
            }else if(c == '[') {
                countStack.addLast(count);
                ansStack.addLast(ans.toString());
                count = 0;//count重新置零
                ans = new StringBuilder();//此段字符串也清零
            }else if(c == ']') {
                //如果遇到右括号，该出栈，出一个数字
                //同时用ans保存最后面的字符，重复之后，再出栈前面的字符，再重复
                //注意ans是全局变量，保证了答案完整
                StringBuilder tmp = new StringBuilder();
                int curCount = countStack.removeLast();
                for(int i = 0; i < curCount; i++){
                    tmp.append(ans);
                }
                ans = new StringBuilder(ansStack.removeLast() + tmp);
            }else{
                ans.append(c);//如果遇到字符，就入栈，
            }
        }
        return ans.toString();
    }
}

二、递归

一般来说，可以用栈解决的问题也能很容易联想到递归，但是这个题写起来并不容易。（我写了一下午没写出来，最后去抄答案，路漫漫啊）

递归的思路就是这样的，这个递归方法是为了解析字符串：

如果遇到了数字，那获取到完整的count，接着要把后面的字符串进行解析，然后重复count次，也就是调用本身进行递归；
如果遇到的是字符，那么就加上去，然后返回给上一级让他去重复count次；
如果遇到的是前括号，什么也不用做，继续游走就可以；

如果遇到的是后括号，返回，因为这一层递归没有任何字符串的收益。

class Solution {

String src;
int ptr;
public String decodeString(String s) {
    src = s;
    ptr = 0;//指针
    return getString();//调用递归方法
}
public String getString() {
    if (ptr == src.length() || src.charAt(ptr) == ']') {
        return "";
    }
    char cur = src.charAt(ptr);//
    int count = 1;
    String ret = "";
    if (Character.isDigit(cur)) {
        // 解析数字
        count = getDigits();
        // 过滤左括号
        ++ptr;
        // 解析 String，这里，在左括号和右括号中间就开始递归。
        String str = getString();
        // 过滤右括号
        ++ptr;
        //接着把处理好的子字符串进行拼接
        while (count-- > 0) {
            ret += str;
        }
    } else if (Character.isLetter(cur)) {
        // 解析 Char
        ret = String.valueOf(src.charAt(ptr++));
    }
    //最后返回
    return ret + getString();
}
//解析数字的方法
public int getDigits() {
    int ret = 0;
    while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
        ret = ret * 10 + src.charAt(ptr++) - '0';
    }
    return ret;
}