LeetCode-394. Decode String(DFS)

Datetime:2017-04-02 05:28:36         Topic: LeetCode          Share        Original >>
Here to See The Original Article!!!

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);  
    }  
};







New