394. Decode String

One way to solve the problem is DFS. But the trick is the input index. The index must be reference (or pointer) because it should be continuous to the function call in the stack.

1:  class Solution {  
2:  public:  
3:    string decodeString(string s) {  
4:      int i = 0;  
5:      return helper(s, i);  
6:    }  
7:    string helper(string s, int &i) {  
8:      string res;  
9:      while (i < s.size() && s[i] != ']') {  
10:        if (!isDigit(s[i])) res += s[i++];  
11:        else {  
12:          int n = 0;  
13:          while (i < s.size() && isDigit(s[i])) n = n * 10 + s[i++] - '0';  
14:          i++; // '['  
15:          string t = helper(s, i);  
16:          i++; // ']'  
17:          for (int j = 0; j < n; j++) res += t;  
18:        }  
19:      }  
20:      return res;  
21:    }  
22:    bool isDigit(char c) {  
23:      return c >= '0' && c <= '9';  
24:    }  
25:  };