## Monday, July 24, 2017

### [Leetcode] Decode String, Solution

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".
```

[Thoughts]

[Code]
``````1:    string decodeString(string s) {
2:      stack<int> repeat_counts;
3:      stack<string> pre_fix;
4:
5:      int num = 0;
6:      string decoded = "";
7:      string cur = "";
8:
9:      s = "1[" + s +"]"; // wrap the input into a bracket to simplify the logic
10:      for(int i = 0; i< s.size(); i++) {
11:        if(isdigit(s[i])) {
12:          num = num*10 + s[i] -'0';
13:          continue;
14:        }
15:
16:        if(s[i] == '[') {
17:          repeat_counts.push(num);
18:          num = 0;
19:          pre_fix.push(cur);
20:          cur = "";
21:          continue;
22:        }
23:
24:        if(s[i] == ']') {
25:          int repeat = repeat_counts.top();
26:          repeat_counts.pop();
27:          string prefix = pre_fix.top();
28:          pre_fix.pop();
29:
30:          cur = prefix + repeatString(cur, repeat);
31:          continue;
32:        }
33:
34:        cur += s[i];
35:      }
36:
37:      return cur;
38:    }
39:
40:    string repeatString(string& organic, int repeats) {
41:      string result = "";
42:      for(int i =0; i< repeats; i++) {
43:        result += organic;
44:      }
45:
46:      return result;
47:    }
``````