A neat and fast (beats 99.38% ~100%) C++ solution


  • 1

    Given an input n, instead of thinking the solution F(n) as the collection of each string in F(n-2) appending proper prefix&suffix character(says, 0,1,6,8,9), to me this is more like a combination problem described as follows:
    "enumerate all possible combinations of 0,1,6,8,9 to form string with length = n/2, as the left half of the strobogrammatic number , where 0,1,6,8,9 can be chosen repeatedly arbitrarily many times."
    Why only the left half? because the right half is determined as well.

    The code:

        vector<string> findStrobogrammatic(int n) {
            vector<string> ret;
            string buf(n,'x'); // or whatever
            collect(0,n-1,buf,ret);
            return ret;
        }
        void collect(int i, int j, string& buf,vector<string>& result) {
            if(i>j)return result.push_back(buf); 
            static const char* table1 = "01869";
            static const char* table2 = "01896";
            int lo = (i==j||i) ? 0 : 1;
            int hi = i==j ? 3 : 5;
            do {
                buf[i] = table1[lo];
                buf[j] = table2[lo];
                collect(i+1,j-1,buf,result);
            } while(++lo < hi);
        }
    

    Here I'm explaining some variable in function 'collect':

    the input 'i', 'j' is the indices of the output string, walking forward and backward, respectively. The function 'collect' is to put proper "mutually" strobogrammatic number at position 'i','j'.

    the entries with the same index in 'table1' and 'table2' are mutually strobogrammatic.

    'lo' is the beginning position of the table; if 'i' is the first position of the string, then we cannot put 0 unless the the total string length is 1 (and the solution is {0,1,8}).

    'hi' is the (excluding) ending position of the table; if the position is right at the center, then the number must have itself to be its strobogrammatic number. In this case, we can only put 0,1,8, so we choose 'hi' = 3.

    I like this implementation myself for some reasons:

    1. The code is fast because it doesn't require any unnecessary memory allocation and excessive copy on the std::string.
    2. What number to put in is determined by the indice 'lo'/'hi' so the while loop is very clean; besides, the corner case is handled by very simple logic.

    (I am willing to hear your criticism.)


  • 0
    A

    I made a similar solution, just purely iterative. I do like your lo/hi thing, which is more concise than my if/else special casing.

    class Solution {
    public:
        vector<string> findStrobogrammatic(int n) {
            vector<string> sln(0);
            string s(n, '0');
            string order = "01698";
            char terminator = order.back();
    
            while(1) {
                if (s[0] != '0' || n == 1) {
                    sln.push_back(s);
                }
                
                for (int i = 0, j = n-1; i <= j; i++, j--) {
                    if (s[i] == terminator) {
                        s[i] = '0'; s[j] = '0';
                        if (j - i <= 1) {
                            return sln;
                        }
                        continue;
                    }
                    s[i] = order[order.find(s[i])+1];
                    if (i!=j) {
                        s[j] = (s[i] == '6') ? '9' : (s[i] == '9') ? '6' : s[i];
                    } else if(s[i] == '6') {
                        s[i] = terminator; s[j] = terminator;
                    }
                    break;
                }
            }
            return sln;
        }
    };
    
    

Log in to reply
 

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