394. Decode String.java

题目要求：b3[a2[c]d]e => b accd accd accd e (不带空格，只是为了看着方便）

class Solution {
    public String decodeString(String s) {
        //看过最优解(56答案中的135)，自己写
        //1. stack
        StringBuilder cur = new StringBuilder();
        Stack<Integer> intStack = new Stack<>();
        Stack<StringBuilder> strStack = new Stack<>();
        int k = 0;
        for(char c : s.toCharArray()){
            if(Character.isDigit(c)){
                k = k * 10 + c - '0';
            }else if(c == '['){
                intStack.push(k);
                strStack.push(cur);
                k = 0;
                cur = new StringBuilder();
            }else if(Character.isLetter(c)){
                cur.append(c);
            }else{   //']'
                StringBuilder temp = cur;
                cur = strStack.pop();
                int times = intStack.pop();
                while(times-- > 0){
                    cur.append(temp);
                }
            }  
        }
        return cur.toString();
    }
//可以进而优化为1个stack<StrItem>  其中StrItem为新构建类：{int count; StringBuilder sb)    
  
  //2. DFS 稍微不好理解，自己没有实现，但最后看懂了
  // 举例： b3[a2[c]d]e
class Solution {
public String decodeString(String s, int i) { //从第i位开始解析s
        StringBuilder res = new StringBuilder();
        while (i < s.length() && s.charAt(i) != ']') { //不要忘记 !=']'
            if (!Character.isdigit(s.charAt(i))) //字母直接append，i++
                res.append(s.charAt(i++));
            else {                              //数字
                int n = 0;
                while (i < s.length() && Character.isdigit(s.charAt(i)))
                    n = n * 10 + s.charAt(i++) - '0';       //避免多位情况，如32要处理32次，因此先处理n的值
                i++; // 上一步走完i到'['，这一步i++之后，i停在[之后的第一个字符处
                String t = decodeString(s, i);  //t得到的是[]之间的字符串解析（因为while循环条件中有不等于]，所以不会走到]）
                i++; // ']'
                while (n-- > 0) //每个[]结束时，就要按次数开始循环输出decode结果了
                    res.append(t);
            }
        }
        return res.toString();
    }

    public String decodeString(String s) {
        return decodeString(s, 0);
    }
};
     
 /* 之前自己思路没考虑：1. 嵌套情况如3[a2[c]]，因此必须考虑stack或者DFS；2. 对于数字没考虑多位情况，如23a；3.没搞清变量生效范围,应定义在外面

}