> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dfs-and-bfs/394.-decode-string.md).

# 394. 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:**

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

```cpp
// Recursion
string decodeHelper(const string& s, int& i) {
    string res;
    while (i < s.length() && s[i] != ']') {
        // add character directly
        if (s[i] < '0' || s[i] > '9') {
            res += s[i++];
        } else {
            int num = 0;
            while (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s[i++] - '0');
            }
            ++i; // Skip '['
            string tmp = decodeHelper(s, i);
            ++i; // Skip ']'
            while (num-- > 0) {
                res += tmp; 
            }
        }
    }
    return res;
}
string decodeString(string s) { // time: O(n); space: O(n)
    int i = 0;
    return decodeHelper(s, i);
}
```

```cpp
// Iteration
string decodeString(string s) { // time: O(n); space: O(n)
    string str;
    int num = 0;
    stack<int> st_num;
    stack<string> st_str;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] >= '0' && s[i] <= '9') {
            num = num * 10 + (s[i] - '0');
        } else if (s[i] == '[') {
            st_num.push(num);
            num = 0;
            st_str.push(str);
            str.clear();
        } else if (s[i] == ']') {
            int k = st_num.top(); st_num.pop();
            while (k-- > 0) {
                st_str.top() += str;
            }
            str = st_str.top(); st_str.pop();
        } else { // s[i] is char
            str += s[i];
        }
    }
    return str;
}
```