# LeetCode – Decode String

### 题目：

Given an encoded string, return its 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".
```

### 解题：

1. 循环处理的条件是到了字符串的末尾或遇到’]’;
2. 遇到数字记录到循环次数n，跳过'[‘,进入递归处理；
3. 字符串处理功能：通过res将那个处理结果字符串累加。
4. 递归处理完成后跳过’]’；

### 实现：

``````class Solution {
public:

string decodeString(string s) {
int i=0;
return decodeStringHelper(s, i);
}
string decodeString(const string &s, int &i){

string res;
while(i<s.length() && s[i]!=']'){
if (!isdigit(s[i])) {
res += s[i++];
}
else {
int n = 0;
while(i<s.length() && isdigit(s[i])){
n = n*10 + s[i++]-'0';
}
i++;  // [
string t = decodeString(s, i);
i++;  // ]
while(n-->0){  // k times
res += t;
}
}
}
return res;
}
};``````

### 解题：

1. 遇到字符类型字符串，更新计数n；
2. 遇到'[‘ ,计数压栈，临时字符串变量tmp压栈；
3. 遇到’]’, 取出数字和对应字符串栈的数据，重复n倍；
4. 遇到字母直接加到临时字符串变量tmp中。

### 实现：

``````class Solution {
public:
string decodeString(string s) {
string tmp;
stack<int> numStack;
stack<string> strStack;
int n= 0;
for (int i=0;i<s.size();i++){
if (isdigit(s[i])){
n = n*10+s[i]-'0';
}
else if (s[i] == '['){
numStack.push(n);
n = 0;
strStack.push(tmp);
tmp.clear();
}
else if (s[i] == ']'){
int k = numStack.top();
numStack.pop();

while(k-->0) // K
{
strStack.top() +=tmp;
}
tmp = strStack.top();
strStack.pop();

}
else
tmp += s[i];
}
return strStack.size() == 0 ? tmp : strStack.top();
}
};

``````