Leetcode 248 Solution

This article provides solution to leetcode question 248 (strobogrammatic-number-iii)
Categories:
Tags:
Access this page by simply typing in "lcs 248" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/strobogrammatic-number-iii

Solution

class Solution {
public:
    vector<string> findStrobogrammatic(int n, bool allowLeadingZero, const string& left, const string& right)
    {
        vector<string> res;



        if (n == 0)
            res.push_back("");
        else if (n == 1)
        {
            if (allowLeadingZero == false)
            {
                if (left <= "0" && "0" <= right)
                    res.push_back("0");
                if (left <= "1" && "1" <= right)
                    res.push_back("1");
                if (left <= "8" && "8" <= right)
                    res.push_back("8");
            }
            else
            {
                res.push_back("0");
                res.push_back("1");
                res.push_back("8");
            }
            return res;
        }
        else
        {
            auto subres = findStrobogrammatic(n - 2, true, left, right);
            for (auto sub : subres)
            {
                if (allowLeadingZero)
                {
                    res.push_back("0" + sub + "0");
                    res.push_back("1" + sub + "1");
                    res.push_back("6" + sub + "9");
                    res.push_back("8" + sub + "8");
                    res.push_back("9" + sub + "6");
                }
                else
                {
                    string target = "1" + sub + "1";
                    if (left <= target && target <= right)
                        res.push_back(target);



                    target = "6" + sub + "9";
                    if (left <= target && target <= right)
                        res.push_back(target);



                    target = "8" + sub + "8";
                    if (left <= target && target <= right)
                        res.push_back(target);



                    target = "9" + sub + "6";
                    if (left <= target && target <= right)
                        res.push_back(target);
                }
            }
        }



        return res;
    }



    int strobogrammaticInRange(string low, string high) {
        int n1 = low.size();
        int n2 = high.size();



        int res = 0;
        for (int i = n1; i <= n2; i++)
        {
            string left = i == n1 ? low : string(i, '0');
            string right = i == n2 ? high : string(i, '9');



            res += findStrobogrammatic(i, false, left, right).size();
        }



        return res;
    }
};