> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/stack-and-queue/394.-decode-string.md).

# 394. Decode String

![](/files/OX5VO3WDNl5n9MZQyVMV)

![](/files/ntOb1h80SGA3z8lMYTKI)

## two stack

```
time: O(n)
space: O(s1+s2), stack space
```

use this

```java
class Solution {
    public String decodeString(String s) {
        Deque<String> strStack = new ArrayDeque<>();
        Deque<Integer> numStack = new ArrayDeque<>();
        StringBuilder cur = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                int i0 = i;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    i++;
                }
                int num = Integer.valueOf(s.substring(i0, i));
                numStack.push(num);
                strStack.push(cur.toString());
                cur = new StringBuilder();
                
            } else if (s.charAt(i) == ']') {
                
                int repeat = numStack.pop();
                String temp = cur.toString();
                for (int j = 0; j < repeat-1; j++) {
                    cur.append(temp);
                }
                cur = new StringBuilder(strStack.pop() + cur);
                
            } else if (Character.isLetter(s.charAt(i))) {
                cur.append(s.charAt(i));
            }
        }
        return cur.toString();
    }
}

/*
number: add number to number, cur str stack
1. number add to num stack, 因為 num 後面就是 [, so add cur to str stack too, clear cur
2. char: add to cur
3. 遇到 ], num 出戰, str 出站, num*str => set to cur 

     aaa 
3    ""
num. str

cur aaa -> ""

     
2    
num. str

cur aaabcbc => ans
*/
```

```java
/*
"3[a2[c]]"

countStack: 3  ⇒ 2

resStack: "" ⇒ a

res ""  ⇒ a ⇒ "" c

meets ]

sb(a) + cc ⇒ res = acc

meets ]

countStack: 3

resStack: ""

res acc

sb("") + 3*acc

res = accaccacc

1. number ⇒ push countStack ⇒ number push

 2. '[' ⇒ push resStack ⇒ when '[', push res into it

1. char: add char 

1. ']' ⇒ pop

time: O(n)
space: O(s1+s2), stack space
*/
class Solution {
    public String decodeString(String s) {
        Deque<String> resStack = new ArrayDeque<>();
        Deque<Integer> numStack = new ArrayDeque<>();
        int i = 0;
        StringBuilder res = new StringBuilder();
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num*10 + (s.charAt(i) - '0');
                    i++; // 最後會到下一位, 也就是多加了一次
                }
                numStack.push(num);
                i--; // 外層有個i++, 所這要 i--
            } else if (s.charAt(i) == '[') {
                resStack.push(res.toString());
                res = new StringBuilder();
                
            } else if (s.charAt(i) == ']') {
                StringBuilder temp = new StringBuilder(resStack.pop());
                int times = numStack.pop();
                for (int j = 0; j < times; j++) {
                    temp.append(res);
                }
                res = temp;
            } else {
                res.append(s.charAt(i));
            }
            i++;
        }
        return res.toString();
    }
}




/*
2 stack

d3[a]2[bc]d



3
numStack



when [, push to resStack
resstack



res+=letter


res = d

3
numStack

[

res = ""

d         3 
resstack  numStack


res = "a"

d         3 
resstack  numStack

]
res = "a"

d         3 
resstack  numStack


d3[a]2[bc]d

res = bc
daaa          2
resstack  numStack

res = daaabcbcd


*/
```

## one stack

```java
class Solution {
    public String decodeString(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ']') {
                
                List<Character> list = new ArrayList<>();
                while (stack.peek() != '[') {
                    list.add(stack.pop());
                }
                stack.pop(); // [
                int base = 1;
                int k = 0;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    k += (stack.pop() - '0')*base;
                    base *= 10;
                }
                while (k != 0) {
                    for (int j = list.size()-1; j >= 0; j--) {
                        stack.push(list.get(j));
                    }
                    k--;
                }
                
            } else {
                stack.push(s.charAt(i));
            }
        }
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
            res.append(stack.pop());
        }
        return res.reverse().toString();
    }
}

/*
3[a2[c]]

c
[
2
a
[
3
*/
```

## recursion

T: O(k\*n), k is call dfs times, n is String length

S: O(n)

```java
class Solution {

    public String decodeString(String s) {
        return dfs(s, 0)[0];
    }
    private String[] dfs(String s, int i) {
        StringBuilder res = new StringBuilder();
        
        int num = 0;
        while(i < s.length()) {
            if(Character.isDigit(s.charAt(i))) { 
                num = num * 10 + (s.charAt(i) - '0'); 
            } else if(s.charAt(i) == '[') { // when [, call dfs(s, i+1) get str in [ str ]
                
                String[] tmp = dfs(s, i + 1);
                i = Integer.parseInt(tmp[0]);
                
                for (int j = 0; j < num; j++) { // multi str, num needs set back to 0
                    res.append(tmp[1]);
                }
                num = 0;
            } else if(s.charAt(i) == ']') { // when end, return String
                return new String[] { String.valueOf(i), res.toString() };
                
            } else { // letter, add
                res.append(s.charAt(i));
            }
            i++;
        }
        return new String[] { res.toString() };
    }
}

/*
d3[a2[c]]d
    /
   a2[c]
   /
   c
   
   so when back, we can deal with number and decoded String
    => 2c => cc
    => acc
    => 3acc
    => daccaccaccd
*/
```

or i as global variable

```java
class Solution {
    int i = 0;
    public String decodeString(String s) {
        return dfs(s);
    }
    private String dfs(String s) {
        StringBuilder res = new StringBuilder();
        
        int num = 0;
        while(i < s.length()) {
            if(Character.isDigit(s.charAt(i))) { 
                num = num * 10 + (s.charAt(i) - '0'); 
            } else if(s.charAt(i) == '[') { // when [, call dfs(s, i+1) get str in [ str ]
                i++;
                String tmp = dfs(s);                
                for (int j = 0; j < num; j++) { // multi str, num needs set back to 0
                    res.append(tmp);
                }
                num = 0;
            } else if(s.charAt(i) == ']') { // when end, return String
                return res.toString();
                
            } else { // letter, add
                res.append(s.charAt(i));
            }
            i++;
        }
        return res.toString();
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://timmybeeflin.gitbook.io/cracking-leetcode/stack-and-queue/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.