# 0394. Decode String

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Decode String](https://leetcode.com/problems/decode-string/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0394-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]`.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= s.length <= 30`
* `s` consists of lowercase English letters, digits, and square brackets `'[]'`.
* `s` is guaranteed to be **a valid** input.
* All the integers in `s` are in the range `[1, 300]`.

```
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Input: s = "3[a2[c]]"
Output: "accaccacc"

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Use **stack** to record the following information in a tuple **before the left square bracket `[`:**

* **Decoded string** a&#x73;**`pre_DecodedStr`**
* **n times** a&#x73;**`nTimes`**
  {% endhint %}

When **meeting the right square bracket `]`, pop the tuple** from the stack. We then concatenate the returned string by **`pre_DecodedStr + nTimes * cur_DecodedStr`**
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def decodeString(self, s: str) -> str:
        
        # ==================================================
        #  String + Stack                                  =
        # ==================================================
        # time  : O(n)
        # space : O(m), m is the number of pairs of square brackets
        
        ans, stack, curNum = '', [], 0
        
        for char in s:
            if char.isdigit():
                curNum = curNum * 10 + int(char)
                
            elif char == '[':
                stack.append((ans, curNum))
                ans, curNum = '', 0
                
            elif char == ']':
                prev, num = stack.pop()
                ans = prev + num * ans
                
            else:
                ans += char
        
        return ans
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(m), m is the number of pairs of square brackets
     */
    
    public String decodeString(String s) {
        int curNum = 0;
        String ans = "";
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        
        for(int i=0 ; i<s.length() ; i++) {
            char c = s.charAt(i);
            
            if(Character.isDigit(c)) {
                curNum = curNum * 10 + (c - '0');
                
            } else if(c == '[') {
                numStack.push(curNum);
                strStack.push(ans);
                curNum = 0;
                ans = "";
                
            } else if(c == ']') {
                String prev = strStack.pop();
                int num = numStack.pop();
                ans = prev + ans.repeat(num);
                
            } else {
                ans += c;
            }
        }
        
        return ans;
    }
}
```

{% endtab %}
{% endtabs %}