Sharing my 44ms C++ solution


  • 1
    T
    class Solution {
    private:
        void findStrobogrammaticHelper(string s, vector<string>& result, int n, int length)
        {
            if(length==n)
            {
                if(n==1 || s[0]!='0')
                    result.push_back(s);
                return;
            }
            
            string temp = '0' + s + '0';
            int last = temp.length()-1;
            findStrobogrammaticHelper(temp, result, n, length+2);
            
            temp[0] = '1';
            temp[last] = '1';
            findStrobogrammaticHelper(temp, result, n, length+2);
            
            temp[0] = '8';
            temp[last] = '8';
            findStrobogrammaticHelper(temp, result, n, length+2);
            
            temp[0] = '6';
            temp[last] = '9';
            findStrobogrammaticHelper(temp, result, n, length+2);
            
            temp[0] = '9';
            temp[last] = '6';
            findStrobogrammaticHelper(temp, result, n, length+2);
        }
        
    public:
        vector<string> findStrobogrammatic(int n) {
            vector<string> result(0);
            string s;
            
            if(n%2==0)
            {
                s = "";
                findStrobogrammaticHelper(s, result, n, 0);
            }
            else
            {
                s = "1";
                findStrobogrammaticHelper(s, result, n, 1);
                s = "8";
                findStrobogrammaticHelper(s, result, n, 1);
                s = "0";
                findStrobogrammaticHelper(s, result, n, 1);
            }
            
            return result;
        }
    };

Log in to reply
 

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