# 394 Decode String

## 394. [Decode String](https://leetcode.com/problems/decode-string/description/)

## 1. Question

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

## 2. Implementation

**(1) Stack**

思路：这题和Basic Calculator很像，都是在scan输入字符串的过程中，当遇到特定的符号时，将之前处理的变量进行一些操作。Basic Calculator是进行四则运算，这里则是decode。所以对于这类问题，stack非常合适。但有一些不同的是，这里不仅要处理数字，还有string，所以我们用两个stack：num和letters 分别存放数字和已经decode的string。

(1) 当遇到数字时，处理方式和Basic Calculator一样，这里我们存放在count这个变量里，当遇到字母时，放在一个StringBuilder里，这里我们将这个StringBuilder命名为 res

(2) 当遇到'\['时，说明有新的一部分需要decode，将之前得到count和res, 存放在不同的两个stack，并将两个变量的值清空

(3) 当遇到']'时，说明有一部分已经decode完成，从num中pop出数字，从letters中pop出之前已经decode的string，按照数字把当前获得的string加到已经解析的string的部分

```java
class Solution {
    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int count = 0;
        Stack<Integer> num = new Stack<>();
        Stack<StringBuilder> letters = new Stack<>();
        StringBuilder res = new StringBuilder();
        StringBuilder curStr = null;

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                count = 10 * count + c - '0';
            }
            else if (c == '[') {
                num.push(count);
                letters.push(res);
                count = 0;
                res = new StringBuilder();
            }
            else if (c == ']') {
                curStr = res;
                res = letters.pop();
                for (int i = num.pop(); i > 0; i--) {
                    res.append(curStr);
                }
            }
            else {
                res.append(c);
            }
        }
        return res.toString();
    }
}
```

**(2) DFS**

```java
public class Solution {
    public String decodeString(String s) {
        int[] index = new int[1];
        return dfs(s, index);
    }

    public String dfs(String s, int[] index) {
        String res = "";
        int len = s.length();
        int count = 0;

        while (index[0] < len) {
            if (Character.isDigit(s.charAt(index[0]))) {
                count = 10 * count + s.charAt(index[0]) - '0';
            }
            else if (s.charAt(index[0]) == '[') {
                // Skip '['
                ++index[0];
                String nextStr = dfs(s, index);
                while (count > 0) {
                    res += nextStr;
                    --count;
                }
            }
            else if (s.charAt(index[0]) == ']') {
                return res;
            }
            else {
                res += s.charAt(index[0]);
            }
            ++index[0];
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

Stack: 时间复杂度O(n), 空间复杂度O(n)

DFS: 时间复杂度O(n), 空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/stack/394-decode-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.