Decode String

Given an encoded string, return it's decoded string.

The encoding rule is:k[encoded_string], where theencoded_stringinside the square brackets is being repeated exactlyktimes. Note thatkis guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,k. For example, there won't be input like3aor2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

分析

递归，主循环里分别判断isDigit, isLetter和"]"

isDigit 得到数字并且跳过[，递归得到子字符串，然后循环加入结果

isletter 相加得到字符串

] 退出该次循环，返回结果

注意这里i用int[]来得到i的引用，否则主程序里无法得到更新的i继续

用stingbuilder来提高效率

class Solution {
    public String decodeString(String s) {
        StringBuilder str = new StringBuilder(s);//空间效率
        int[] i = new int[1];//传引用
        i[0] = 0;
        return decodeString(s, i);
    }
    String decodeString(StringBuilder s, int[] i){
        // && s.charAt(i[0]) != ']'
        // int n = 0;
        StringBuilder ret = new StringBuilder();
        while(i[0] < s.length()){
            if(Character.isLetter(s.charAt(i[0]))){
                ret.append(s.charAt(i[0] ++));
            }else if(Character.isDigit(s.charAt(i[0]))){
                int n = 0;
                while(Character.isDigit(s.charAt(i[0]))){
                    n = n * 10 + s.charAt(i[0] ++) - '0';//不是+=这里
                }                                             
                i[0] ++; //"["
                String ds = decodeString(s, i);
                while(n -- > 0){
                      ret.append(ds);
                    }
            }else if(s.charAt(i[0]) == ']'){
                i[0] ++;
                return ret.toString();
            }
        }  

        return ret.toString();
   }              

}

用栈，数字栈和字母栈

数字时，入数字栈

字母时，累加得到res

[ 字母res入栈

] 数字字母出栈，得到新res，新res不要在此处入栈！！！！！

class Solution {
    public String decodeString(String s) {
        Stack<Integer> cnt = new Stack<Integer>();
        Stack<String> str = new Stack<String>();
        String res = new String();
        int idx = 0;
        while(idx < s.length()){
            if(Character.isDigit(s.charAt(idx))){//数字入栈
                int n = 0;
                while(Character.isDigit(s.charAt(idx))){
                    n = n * 10 + s.charAt(idx ++) - '0';
                }
                cnt.push(n);
            }else if(s.charAt(idx) == '['){ //字母入栈
                str.push(res);
                res = "";
                idx ++;
            }else if(s.charAt(idx) == ']'){//出栈
                StringBuilder temp = new StringBuilder(str.pop());
                int time = cnt.pop();
                while(time -- > 0){
                    temp.append(res);   //这里append 还是用stringbuilder                 
                }
                res = temp.toString();//关键步骤，此处更新res就好，不必加入stack，让'['时处理
                idx ++;
            }else{
                res += s.charAt(idx ++); //可以直接char相加得到string
            }
        }
        return res;
    }


}