I think my solution using recursion is very easy to understand, but what's the time complexity? Please help me.


  • 1
    S
     vector<string> findStrobogrammatic(int n) {
        vector<string> result = internal_findStrobogrammatic(n);
        
        //Remove number starting with 0
        if(n>1)
        {
            result.erase(std::remove_if(result.begin(), 
                              result.end(),
                              [](string s){return s[0] == '0';}),
               result.end());
        }
        
        return result;
    }
    
    vector<string> internal_findStrobogrammatic(int n) {
        vector<string> result;
        
        if(n == 0)
            return result;
        if(n == 1)
        {
            return {"0","1","8"};
        }
        if(n == 2)
        {
            return {"11","88","69","96","00"};
        }
        
        unordered_map<char,char> numberMap = {{'1','1'},{'8','8'},{'6','9'},{'9','6'},{'0','0'}};
        
        vector<string> prevResult = internal_findStrobogrammatic(n-2);
        
        //start build the string in the center and expand to both sides
        for(string& s:prevResult)
        {
            for(auto pair:numberMap)
            {
                result.push_back(pair.first+s+pair.second);
            }
        }
        
        return result;
    }

Log in to reply
 

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