题解 | #牛牛的字符串解码问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String decodeString (String s) {
        // write code here
        Stack<String> digits=new Stack<>();
        Stack<String> letters=new Stack<>();
        for(char c:s.toCharArray()){

            if(c>='0' && c<='9'){
                digits.push(c+"");
            } else if(c=='[' || c>='a' && c<='z'){
                letters.push(c+"");
            } else if(c==']'){
                StringBuilder tmp1=new StringBuilder();
                for(;!letters.isEmpty();){
                    String x=letters.pop();
                    if(!x.equals("[")){
                        tmp1.insert(0,x);
                    } else {
                        break;
                    }
                }
                int cnt=Integer.parseInt(digits.pop());
                StringBuilder tmp2=new StringBuilder();
                while(cnt>0){
                    tmp2.append(new String(tmp1));
                    cnt--;
                }
                letters.push(new String(tmp2));
            }
        }

        StringBuilder ans=new StringBuilder();
        while(!letters.isEmpty()){
            ans.insert(0, letters.pop());
        }
        return ans.toString();
    }
}

这个代码是我看了另一位牛客同学的代码之后凭借记忆写出来的。我第一次的代码没有考虑括号嵌套括号的情况，所以只有50%的正确率。现在，我使用栈 letters 保存遍历过程的字符，使用栈 digits 保存遇到的数字，因为我们要先匹配最内层的括号，所以遇到 "]" 我们就要在 letters 中把 "[" 之前的字符弹出来保存到 tmp1，接着把 digits 中的数字弹出来保存为 cnt ，然后把这些弹出来的字符重复 cnt 次之后保存到 tmp2，然后把 tmp2 保存到 letters 用于下一次重复。循环完整个字符串 s，就把 letters 中的字符串弹出来保存到结果字符串 ans。注意要用 insert 把字符插入到 StringBuilder 以保证字符的顺序不发生变化。