# LeetCode – Decode String
Date: 2019-10-16


### **题目：**

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();
    }
};

```