Decode String

394. Decode String

Difficulty: Medium

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

The encoding rule is: k[encoded_string], where the _encoded_string_ inside the square brackets is being repeated exactly _k_ times. Note that _k_ is 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 like 3a or 2[4].

Examples:

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

Solution

递归写法

class Solution {
    public int pos=0;
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder("");
        StringBuilder num = new StringBuilder("");
                
        for(int i=pos;i<s.length();++i){
            char c = s.charAt(i);
            // 匹配 [
            if(c=='['){
                pos = i+1;
                String next = decodeString(s);
                for(int n = Integer.parseInt(num.toString());n>0;n--)sb.append(next);
                num = new StringBuilder(""); // 还原num
                i = pos; //记得更新pos
            // 匹配 ]
            }else if(c==']'){
                pos=i;
                break;
                
            // 匹配数字
            }else if(Character.isDigit(c)){
                num.append(c);
            // 匹配字母
            }else{
                sb.append(c);
            }
            
        }
        return sb.toString();
    }

}

非递归写法

class Solution {
    public String decodeString(String s) {
        Stack<Integer> intStack = new Stack<>();
        Stack<StringBuilder> strStack = new Stack<>();
        StringBuilder cur = new StringBuilder();
        int k = 0;
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                k = k * 10 + ch - '0';
            } else if ( ch == '[') {
                intStack.push(k);
                strStack.push(cur);
                cur = new StringBuilder();
                k = 0;
            } else if (ch == ']') {
                StringBuilder tmp = cur;
                cur = strStack.pop();
                for (k = intStack.pop(); k > 0; --k) cur.append(tmp);
            } else cur.append(ch);
        }
        return cur.toString();
    }

}