Share my 16ms C++ solution and thoughts


  • 0
    H

    I noticed there are so many different performance so I want to know how much better I can do. I spent about 3 hours on it. I think the code below is easy to understand, although Helper() might be improved. The increase() function is used to determine whether we increase the return value.

    The most time consuming part is that I think we need to generate the strings. Otherwise there might be some subtle cases that is hard to compare. Suppose we have M strings from layer n-2, and we now generate length n string. Without knowing exactly the details of M strings, how can we know whether this length n string is within the range, if the range itself is length n?

    Key parts:
    1, recursion on a single string, not on a vector of strings. For example, following is not efficient:

    GenerateBad(int n, vector<string> &path...){
        ........
        vector<string> smallerPath;
        GenerateBad(n-2, smallerPath...);
        //generate path
    }
    

    Instead, we do DFS on one single string. We just change its chars each time. Using this method for Stobogrammatic II is also good.

    2, recursion from center of string to first char. Only in this way we can calculate how many strings are in the range. Imagine we are now at index=N in Helper(). That means from index=N+1 to n-1-index is already a good string. We can then decide whether to increase the return value, depending on whether it is in the range.
    However, if you recursion from first char to center of string, it is hard to collect the number. This is because, when you are at index=N, you haven't filled the center so you don't have a valid string yet.

    3, try to call increase() function as this problem is subtle. Don't increase return value inside Helper(). Use a different function for it.

    public:
    void increase(string &path, int &number, int index, int n, int lenL, int lenH, string &low, string &high){
        //determine whether to increase number, given we already have a good string of length existL. 
        int existL = (n-1-index - (index) +1);
    
        //out of range, directly return. 
        if (existL<lenL || existL>lenH || (path[index]=='0'&&existL>1))
            return;
    
        //within range, directly increase
        if (existL>=lenL+1 && existL<=lenH-1){
            number++;
        }
        else{
            //these are subtle cases. Try to make it shorter. 
            if (lenL==lenH){
                //only in this case we directly compare string
                if (path.compare(index, existL, low)>=0 && path.compare(index, existL, high)<=0)
                    number++;
            }
            else{
                if (    (path.compare(index, existL, low)>=0 && existL==lenL )  || 
                        (path.compare(index, existL, high)<=0 && existL==lenH) )
                    number++;
            }
        }
    }
    
    //helper function for DFS. Can be improved. 
    void helper(string &path, int n, int index, int lenL, int lenH, string &low, string &high, int &retV){
        //when we reach index, we already have something in the middle, from index+1.
        if(index != (n-1)/2 ){
            //the if block should be before the next if block. 
            increase(path, retV, index+1, n, lenL, lenH, low, high);
        }
        if (index<0){
            return;
        }
    
        if (index==(n-1)/2){
            if (index*2==(n-1)){
                //n is odd number
                for(int i=0; i<3; i++){
                    path[index]=begin[i];
                    if(index>0 || i>0 || n==1){
                        helper(path, n, index-1, lenL, lenH, low, high, retV);
                    }
                }
            } 
            else{
                for(int i=0; i<5; i++){
                    path[index]=begin[i];
                    path[index+1]=end[i];
                    if(index>0 || i>0 || n==1)
                        helper(path, n, index-1, lenL, lenH, low, high, retV);
                }
            }
            return;
        }
    
        int newlowerlayer=0;
        for(int i=0; i<5; i++){
            path[index]=begin[i];
            path[n-index-1]=end[i];
            if(index>0 || i>0 || n==1)
                helper(path, n, index-1, lenL, lenH, low, high, retV);
        }
        
    }
    void findStrobogrammatic(int n, int lenL, int lenH, string &low, string &high, int &retV) {
        string path(n,'0');
        //recursion from middle
        //filling the middle chars first. 
        helper(path, n, (n-1)/2, lenL, lenH, low, high, retV);
    }
    
    int strobogrammaticInRange(string low, string high) {
        int lenL = low.length();
        int lenH = high.length();
        
        if(lenL>lenH || (lenL==lenH && high<low))
            return 0;
    
        int retV=0;
        findStrobogrammatic(lenH,  lenL, lenH, low, high, retV);
        if(lenH>lenL)
            findStrobogrammatic(lenH-1, lenL, lenH, low, high, retV);
        
        return retV;
    }
    

    private:
    char begin[5]={'0','1','8','6','9'};
    char end[5]={'0','1','8','9','6'};


Log in to reply
 

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