Extremely clear C++ solution using recursion, 86 ms


  • 0
    W
    class Solution {
    public:
        int strobogrammaticInRange(string low, string high) {
            int count = 0;
            
            for (int i=(int)low.size(); i<=high.size(); ++i) {
                strobogrammatic(i, count, "", "", low, high);
            }
            
            return count;
        }
        
        bool inRange(string low, string high, string num) {
            if (num[0] == '0' && num.size() > 1) return false;
            bool c1=true, c2=true;
            if (num.size() == low.size()) {
                for (int i=0; i<num.size(); i++) {
                    if (num[i] - low[i] < 0) {
                        c1 = false;
                        break;
                    } else if (num[i] - low[i] > 0) {
                        break;
                    }
                }
            }
            
            if (num.size() == high.size()) {
                for (int i=0; i<num.size(); i++) {
                    if (num[i] - high[i] < 0) {
                        break;
                    } else if (num[i] - high[i] > 0) {
                        c2 = false;
                        break;
                    }
                }
            }
            
            return c1 && c2;
        }
        
        void strobogrammatic(int size, int& count, string prefix, string suffix, string low, string high) {
            if (size == 0) {
                if (inRange(low, high, prefix + suffix)) count++;
                return;
            }
            
            if (size == 1) {
                for (string mid : center) {
                    if (inRange(low, high, prefix + mid + suffix)) count++;
                }
                return;
            }
            
            for (auto p : pairs) {
                strobogrammatic(size - 2, count, prefix + p.first, p.second + suffix, low, high);
            }
        }
        
    private:
        vector<string> center = {"0", "1", "8"};
        unordered_map<string, string> pairs = {
            {"0", "0"},
            {"1", "1"},
            {"6", "9"},
            {"8", "8"},
            {"9", "6"},
        };
    };
    

Log in to reply
 

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