# 394-Decode String
###### tags: `Medium`
## Question
https://leetcode.com/problems/decode-string/
## Key
## Reference
## Solution

string decodeString(string s) {
        string res;
        int num = 0;
        stack<int> stackInt;
        stack<string> stackStr;

        for(char c : s)
        {
            if(c == '[')
            {
               stackInt.push(num);
               num = 0; // reset the times
               stackStr.push(res);
               res = "";
            }
            else if(c == ']')
            {
               int times = stackInt.top();
               stackInt.pop();
               for(int i = 0; i < times; i++)
               {
                   stackStr.top() += res;
               }
               res = stackStr.top();
               stackStr.pop();
            }
            else if(c >= '0' && c <= '9')
            {
                num = num * 10 + c - '0';
                //transfer string  to integer
            }
            else //when c is a char
            {
                res = res + c;
            }
        }

        return res;
    }

### DFS SOL.

boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}