# Leetcode 248 Solution

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 (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)
{
{
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;
}
};
``````