# 394.Decode-String

## 394. Decode String

## 题目地址

<https://leetcode.com/problems/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".
```

## 代码

### Approach #1 Two Stack

数字: countStack.push(count) `[` : resStack.push(res), res = "" `]`: pop, res = temp Else: res+=

```java
class Solution {
  public String decodeString(String s) {
        String res = "";
    Stack<Integer> countStack = new Stack<>();
    Stack<Integer> resStack = new Stack<>();
    int idx = 0;
    while (idx < s.length()) {
      if (Character.isDigit(s.charAt(idx))) {
        int count = 0;
        while (Character.isDigit(s.charAt(idx))) {
          count = 10 * count + (s.charAt(idx) - '0');
          idx++;
        }
        countStack.push(count);
      }
      else if (s.charAt(idx) == '[') {
        resStack.push(res);
        res = "";
        idx++;
      }
      else if (s.charAt(idx) == ']') {
        StringBuilder temp = new StringBuilder(resStack.pop());
        int repeatTimes = countStack.pop();
        for (int i = 0; i < repeatTimes; i++) {
          temp.append(res);
        }
        res = temp.toString();
        idx++;
      }
      else {
        res += s.charAt(idx++);
      }
    }
    return res;
  }
}
```

### Approach #2 DFS

使用一个全局`pos`记录递归位置

`[` 开始递归， `]` 返回结果

```java
class Solution {
  private int pos = 0;
  public String decodeString(String s) {
    StringBuilder sb = new StringBuilder();
    String num = "";
    for (int i = pos; i < s.length(); i++) {
      // 1. 解析数字
           if (Character.isDigit(s.charAt(i))) {
        num += s.charAt(i);
      }
      // 2. '['， dfs递归，并记录pos
      else if (s.charAt(i) == '[') {
        pos = i + 1;
        String next = decodeString(s);
        for (int n = Integer.valueOf(num); n > 0; n--) {
          sb.append(next);
        }
        num = "";
        i = pos;
      } 
      // 3. retrun 结果
      else if (s.charAt(i) == ']') {
        pos = i; // 返回上一层会进入for循环 pos + 1
        return sb.toString();
      } 
      else {
        // 4. letter append
        sb.append(s.charAt(i));
      } 
    }

    return sb.toString();
  }
}
```

### Approach #3 Queue

```java
class Solution {
  public String decodeString(String s) {
    Deque<Character> queue = new LinkedList();
    for (char c: s.toCharArray()) {
      queue.offer(c);
    }
    return bfs(queue);
  }

  private String bfs(Deque<Character> queue) {
    StringBuilder sb = new StringBuilder();
    int num = 0;
    while (!queue.isEmpty()) {
      char c = queue.poll();
      // 1. digit
      if (Character.isDigit(c)) {
        num = num * 10 + c - '0';
      } 
      // 2. `[` 进入bfs递归
      else if (c == '[') {
        String sub = bfs(queue);
        for (int i = 0; i < num; i++) {
          sb.append(sub);
        }
        num = 0;
      }
      // 3. `]` break
      else if (c == ']') {
        break;
      }
      // 4. letter append
      else {
        sb.append(c);
      }
    }

    return sb.toString();
  }
}
```


---

# 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://wentao-shao.gitbook.io/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.