Easy to understand C++ solution


  • 0
    K

    I recurse with n-2 instead of n-1. There are a lot of corner cases to be taken care of. The example doesn't show that double numbers can contain 00, when nested inside a larger number. A single number can contain 0, when nested in a larger number.
    Thus I split the recursion into one function that first works out the corner cases and a second function that calls it self with n-2 until hitting 1 or 2, whichever comes first. Then returning the posisibilities for nested 1 and nested 2 numbers and then recursively just adds the left and right part from double numbers to all the strings returned from the previous recursion.

    class Solution {
    public:
    vector<string> stroboSingle()
    {
    return {"0","1","8"};

    }
    vector<string> stroboDouble()
    {
        return {"11","69","88","96"};
        
    }
    vector<string> stroboDoubleCenter()
    {
        return {"00","11","69","88","96"};
        
    }
    vector<string> stroboDoubleLeft()
    {
        return {"1","6","8","9"};
        
    }
    vector<string> stroboDoubleRight()
    {
        return {"1","9","8","6"};
        
    }
    vector<string> stroboDoubleCenterLeft()
    {
        return {"0","1","6","8","9"};
        
    }
    vector<string> stroboDoubleCenterRight()
    {
        return {"0","1","9","8","6"};
        
    }
    vector<string> findStrobogrammaticHelper(int n){
        if(abs(n)==1)
            return stroboSingle();
        if(abs(n)==2)
            return stroboDoubleCenter();
         vector<string> outString;
        vector<string> doubleStringL=stroboDoubleCenterLeft();
        vector<string>  doubleStringR=stroboDoubleCenterRight();
        vector<string> restString=findStrobogrammaticHelper(abs(n)-2);
        for (int i=0; i<doubleStringL.size();++i)
        {
            for(int j=0; j<restString.size();++j)
            {
                outString.push_back(doubleStringL[i]+restString[j]+doubleStringR[i]);
                
            }
        }
        return outString;
    }
    vector<string> findStrobogrammatic(int n) {
        if(n==0)
        {
            return {""};
        }
        if(abs(n)==1)
            return stroboSingle();
        if(abs(n)==2)
            return stroboDouble();
        vector<string> outString;
        vector<string> doubleStringL=stroboDoubleLeft();
        vector<string>  doubleStringR=stroboDoubleRight();
        vector<string> restString=findStrobogrammaticHelper(abs(n)-2);
        for (int i=0; i<doubleStringL.size();++i)
        {
            for(int j=0; j<restString.size();++j)
            {
                outString.push_back(doubleStringL[i]+restString[j]+doubleStringR[i]);
                
            }
        }
        return outString;
    }
    

    };


Log in to reply
 

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