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".

解题思路

题目一看到，我们应该就想到两种解法，一种是用栈，一种是搜索。这里我直接讲我做的栈的解法。我们定义两个栈，一个用来存储每个"["前的数字，一个用来存储每对[]里面的字符串，一个存储解码后的字符串的StringBuilder sb。

（1）对每个字符进行判断，如果是数字的话，统计完整然后入栈。（这里要注意的是，给的数字可能超过10,比如s = "100[leetcode]"），所以我们要在对每个数字进行*10再加上。

（2）如果遇到了[我们就将前面统计的字符串加入到我们的字符串栈中。然后初始化我们的变量，方便再次存储。

（3）如果遇到了字符，我们将其存储起来。可以用StringBuilder或者StringBuffer，这样子是为了用String相加的话出现的内存限制问题。在上面我们定义的StringBuilder。

（4）如果遇到了]，我们取出在[前存储的字符串temp，只要对字符串栈出栈就可以取到。然后再取出一个[前的数字num，同样对数字栈出栈就可以取到。我们将在temp后面追加num个在[]期间的字符串sb。然后我们再将temp还给我们的sb。如果后面没有字符了，sb就是我们的最后的答案。如果后面还有[，就会回到我们的第二种情况，sb就会再次被存储起来，用于后面的使用。

下面给出参考代码

class Solution {
 public String decodeString(String s) {
        //用来存储字符串里面的数字
        Stack<Integer> num = new Stack<>();
        //用来存储字符串里面每一个中括号内的字符串
        Stack<String> cs = new Stack<>();
        //用来存储解码后的字符串
        StringBuilder sb = new StringBuilder();
        //用来记录[前的数字，防止出现大于10的情况
        int muti = 0;
        for(char i : s.toCharArray()){
            if(Character.isDigit(i)) muti = muti * 10 + (i - '0');
            else if(i == '['){
                //将[之前如果存在连续的字符串添加到字符串栈
                cs.add(sb.toString());
                num.add(muti);
                //添加完需要再次初始化，不然会影响到后面的添加
                sb.delete(0,sb.length());
                muti = 0;
            }else if(Character.isLetter(i)){
                sb.append(i);
            }else{
                //字符为]的情况，取出前面连续的字符串和数字，进行拼接
                StringBuilder temp = new StringBuilder(cs.pop());
                int ans = num.pop();
                for(int j = 0; j < ans; j++) temp.append(sb);
                //将拼接完的字符串赋值给sb，如果后面没了，就是最后的答案。如果还有的话，根据情况进行添加
                sb = temp;
            }
        }
        return sb.toString();
    }
}