# LeetCode-394. Decode String(DFS)

Datetime:2017-04-02 05:28:36         Topic: LeetCode          Share        Original >>

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

```s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

```
```class Solution {
public:
string DFS(string s, int &k)
{
string ans;
int cnt = 0;
while(k < s.size())
{
if(isdigit(s[k])) cnt = cnt*10 + (s[k++]-'0');
else if(s[k]=='[')
{
string tem = DFS(s, ++k);
for(int i = 0; i < cnt; i++) ans += tem;
cnt = 0;
}
else if(s[k]==']')
{
k++;
return ans;
}
else ans += s[k++];
}
return ans;
}

string decodeString(string s) {
int k = 0;
return DFS(s, k);
}
};
```