28ms Recursive C++ solution, beat 100%


  • 0
    C
    class Solution {
    public:
        vector<string> findStrobogrammatic(int n) {
            
            vector<pair<char, char>> stro = {
                pair<char, char>('0','0'),
                pair<char, char>('1','1'),
                pair<char, char>('6','9'),
                pair<char, char>('9','6'),
                pair<char, char>('8','8')
            };
            vector<char> mid = {'0','1','8'};
            vector<string> result;
            
            string s(n, ' ');
            int i = 0;
            int j = n-1;
            if (n == 1){
                for (auto m : mid){
                    s[0] = m;
                    result.push_back(s);
                }       
                return result;
            }        
            gets(stro, mid, result, s, i, j);
            
            return result;
        }   
        
        void gets(vector<pair<char, char>> &stro, vector<char> &mid, vector<string> &result, string &s, int i , int j)
        {
            if (i < j){
                for ( auto v: stro){
                    if (i == 0 && v.first == '0'){
                        continue;
                    }
                    s[i] = v.first;
                    s[j] = v.second;
                    if (j - i == 1)
                        result.push_back(s);
                    else if( j - i == 2){
                        for (auto m : mid){
                            s[i+1] = m;
                            result.push_back(s);
                        }
                    }                    
                    else
                        gets(stro, mid, result, s, i+1, j-1);
                }
            }
        }
    };
    

Log in to reply
 

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