力扣——字符串解码

题目链接：

链接

题目描述：

思路：

思路一

把前面的数据用栈存起来，找到最后的字母，然后出栈，进行拼接

1. 准备一个数字栈和字母栈
2. 准备变量记录当前的数字和字母
3. 遇到【，就要把当前的数字、字母入栈
4. 注意数字范围0~300，所以要把上一个数字10+当前数字（连续出现时），如1 2 ->110+2
5. 注意字母可能有多个，要先拼接成一组完整的载入栈
6. 最后遇到】，就要出栈进行拼接，注意当前的变量只有字母，
7. 拼接时，要出栈 当前字母前面的数字，然后用for循环拼接，再然后出栈上一个字母，拼接到前面
8. 之后就会一直拼接

思路二

用递归实现，递归本身就会调用栈，所以不需要栈来存储数字和字母
什么时候开始递归：遇到【
什么时候递归返回：遍历到字符串末尾、遇到】

1. 遇到【，开始递归，此时的数字是完整的，如21【abc】，此时数字为21，字母为’’
2. 遇到】，停止递归，返回上一级拼接，此时的字母就是完整的，如21【abc】，此时数字为0，字母为abc，所以要把字母返回上一级，同时i也要返回
3. 为什么i要返回，因为实际上我们已经遍历到6了，但是返回到【的时候 i 变成了2，所以要更新 i 避免重复遍历。

实现代码：

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;

        Stack<Integer> stack_multi = new Stack<Integer>();
        Stack<String> stack_res = new Stack<String>();

        for(Character c : s.toCharArray()){
        	//入栈
            if(c == '['){
                stack_multi.push(multi);
                stack_res.push(res.toString());
                multi = 0;
                res = new StringBuilder();
            }
            //拼接
            else if(c == ']'){
                StringBuilder tmp = new StringBuilder();
                int its_multi = stack_multi.pop();
                for(int i = 0; i < its_multi; i++){
                    tmp.append(res);
                }
                res = new StringBuilder(stack_res.pop() + tmp.toString());
            }
			//当前数字
			else if(c >= '0' && c <= '9'){
                multi = multi * 10 + (c - '0');          
            }
            //当前字母
            else{
                res.append(c);
            }
        }
        return res.toString();
    }
}

class Solution {
    public String decodeString(String s) {
        return dfs(s, 0)[0];
    }

    private String[] dfs(String s, int i){
        StringBuilder res = new StringBuilder();
        int multi = 0;
        while(i < s.length()){
            if(s.charAt(i) == '['){
            	//递归
                String[] tmp = dfs(s,i+1);
                //更新i
                i = Integer.parseInt(tmp[0]);
                //拼接
                while(multi > 0){
                    res.append(tmp[1]);
                    multi--;
                }
            }else if(s.charAt(i) == ']'){
            	//返回字母和i
                return new String[] {String.valueOf(i),res.toString()};
            }else if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                multi = multi * 10 + (s.charAt(i) - '0');          
            }else{
                res.append(s.charAt(i));
            }
            i++;
        }
        return new String[] {res.toString()}; //这里用数组是为了兼容上面的 返回字母和i
    }
}