卖萌的弱渣

I am stupid, I am hungry.

Decode String

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:

1
2
3

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

Solution

  • Java
(Decode-String.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Solution {
    public String decodeString(String s) {
        Stack<Integer> intStack = new Stack<Integer>();
        // current string
        StringBuilder cur = new StringBuilder();
        Stack<StringBuilder> strStack = new Stack<StringBuilder>();
        // current number
        int k = 0;
        for(char ch : s.toCharArray()){
            // 持续统计num
            if(Character.isDigit(ch)){
                k = k*10 + ch-'0';
            }
            else if (ch=='['){
                intStack.push(k);
                strStack.push(cur);

                // new cur and k
                cur = new StringBuilder();
                k = 0;
            }
            else if (ch == ']'){
                StringBuilder tmp = cur;
                cur = strStack.pop();
                // generate num*string
                for(k=intStack.pop();k>0;k--) cur.append(tmp);
            }
            // characters
            else cur.append(ch);

        }
        return cur.toString();
    }
}
  • Python
  • stack<string,num> 辅助
(Decode-String.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        num = ""

        stack = []
        stack.append(["",0])
        for ch in s:
            #123456789
            if ch.isdigit():
                num += ch
            elif ch == '[':
                # 插入当前的num
                stack.append(["",int(num)])
                num = ""
            elif ch == ']':
                sub = stack[-1][0]*stack[-1][1]
                stack.pop()
                stack[-1][0] += sub
            else:
                # characters
                stack[-1][0] += ch
        return stack[0][0]