clean fast c++ 0ms code


  • 1
    T

    My solution contains two steps.

    1. For all possible strobogrammatic that length is between low's length and high's length, we just need to calculate their numbers. There is no need to generate all these strobogrammatic. For example, low is "0" and high is "1680", we calculate all 2 and 3 length strobogrammatic. We can use dp to calculate it.
    2. Generate strobogrammatic for length equal to low and high, and check whether they are between low and high.

    '''
    int strobogrammaticInRange(string low, string high) {
    int cnt = 0;
    int len1 = low.length(), len2 = high.length();
    if(len2<len1) return 0;
    if(len1 == len2 && low > high) return 0;

        int dp[2] = {1, 3};
        for(int i=2; i<=len2-1; ++i)
        {
            if(i>=len1+1 && i<=len2-1)
                cnt += dp[i&1] * 4;
            dp[i&1] = dp[i&1] * 5;
        }
        
        string tmp(len1, '0');
        helper(cnt, tmp, low, high, 0, len1-1);
        if(len2 != len1)
        {
            string tmp1(len2, '0');
            helper(cnt, tmp1, low, high, 0, len2-1);
        }
        return cnt;
    }
    void helper(int& res,string& cur, const std::string& low, const std::string& high, int l, int r)
    {
        static vector<std::pair<char, char> > m{{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
        if(l>r)
        {
            if((cur.size() > low.size() || low <= cur) &&
               (cur.size() < high.size() || cur <= high))
                ++res;
            return;
        }
        int start = l==0 && r!=0? 1:0;
        int end = (l==r) ? 2:4;
        for(int i=start; i<=end; ++i)
        {
            cur[l] = m[i].first;
            cur[r] = m[i].second;
            if((cur.size()>low.size() || string(low,0, l+1) <= string(cur,0, l+1)) &&
               (cur.size()<high.size()|| string(cur,0, l+1) <= string(high, 0, l+1)))
                helper(res, cur, low, high, l+1, r-1);
        }
    }
    

    '''


Log in to reply
 

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