Simple C++ recursive solution with explaination [AC]


  • 0

    We will divide our string into a sub-problem when we see a digit and will recursively solve this string.

    class Solution {
    private:
        string helper(string s)
        {
            //base case
            if(s=="")
                return "";
            
            int i=0;
            string res ="";
            int n = s.length();
            while(i<n)
            {
                // if char is not a digit
                if(i<n && !isdigit(s[i]))
                    res+=s[i++];
                
                else
                {
                    // we found a sub problem
                    int num = 0;
                    /// get the digit
                    while(i<n && isdigit(s[i]))
                        num = num*10 + (s[i++]-'0');
                    //i is at now [
                    i++; 
                    
                    int start = i;
                    //get the corresponding closing bracket
                    int k  = 1;
                    while(k)
                    {
                        if(s[i]=='[')
                            k++;
                        else if(s[i]==']')
                            k--;
                        i++;
                    }
                    // recur for the subproblem
                    string decode = helper(s.substr(start,i-start-1));
                    // append the 'num' times the subproblem
                    while(num--)
                        res+=decode;   
                }
            }
            return res;
            
            
        }
    public:
        
        string decodeString(string s) {
            
            return helper(s);
        }
        
        
    };```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.