A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
Example:
Input: low = "50", high = "100"
Output: 3
Explanation: 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the lowand high numbers are represented as string.
Because the range might be a large number, the lowand high numbers are represented as string.
Notes:
This question can be viewed as a follow-up of Strobogrammatic number I and II.
One way to solve this problem is that we can count the number of each length between low and high (inclusive), and then add them together.
The corner case is when the length is the same as that of the low or high, we need to choose the ones inside the range. For easy coding, we can use string.compare() function.
See the code below:
class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int res = 0;
vector<string> ss = {"", "0", "1", "8"};
for(int i = low.size(); i <= high.size(); ++i) {
for(auto &s : ss) {
find(low, high, s, i, res);
}
}
return res;
}
private:
void find(string low, string high, string path, int len, int &res) {
if(path.size() >= len) {
if(path.size() != len || (len != 1 && path[0] == '0')) return;
if(len == low.size() && path.compare(low) < 0) return;
if(len == high.size() && path.compare(high) > 0) return;
++res;
}
vector<string> ss1 = {"0", "1", "6", "8", "9"}, ss2 = {"0", "1", "9", "8", "6"};
for(int i = 0; i<ss1.size(); ++i) {
find(low, high, ss1[i] + path + ss2[i], len, res);
}
}
};
Second Solution:
Apparently, we re-calculate a lot in the above code, since we go over all the possible case (even more than 1 times). For example, for each length, we always start from 0.
There are some rules if we observe carefully.
For example, length = 1, there are 3, "0", "1", and "8", thus dp[1] = 3;
when length = 2, there are five, "00", "11", "69", "88", and "96", but the first one does not valid, thus dp[2] = 4;
Now let us look at the dp[3]. After think for a while, it turn out that they can only be formed by inserting a single number in the middle of that with a length of 2. And there are only 3 valid single numbers. Thus, dp[3] = 3*dp[2];
Now let us look at the dp[4]. Similar to dp[3], the one with length of 4 can be formed by inserting the above one of the basic units with a length of 2 in the middle of that with a length of 2. And there are 5 kinds of these basic unites ("00" now is valid since we insert in the middle). Thus dp[4] = 5*dp[2];
Similarly, dp[5] = 3*dp[4], and dp[6] = 5*dp[4], ...
Thus, dp[2n] = 5^(n-1) * dp[2], dp[2n+1] = 3 * 5^(n-1) * dp[2], where n>0.
So we can just modify the above code to calculate the number of solutions with the same length of low and also no smaller than it; as well as the number of solutions with the same length of high and also no larger than it. To do this, we just need to modify the code for Strobogrammatic Number II a little bit (adding comparison with the low or high, and just recording the valid counts).
The one with lengths in the range can be calculated directly using the above dp table.
See the code below:
class Solution {
public:
int findStrobogrammatic(string low, string high) {
if(low > high) return 0;
if(low == high) return isValid(low) ? 1 : 0;
int res = 0, ct1 = 0, ct2 = 0, len1 = low.size(), len2 = high.size();
vector<string> ss = {"0", "1", "8", "69", "96"};
dfs1(ss, "", low, ct1);
dfs2(ss, "", high, ct2);
res += ct1 + ct2;
vector<int> dp(len2, 0);
dp[0] = 1;//empty string
dp[1] = 3;
dp[2] = 5;
for(int i=3; i<len2; ++i) {
if(i & 1) dp[i] = 3 * dp[i-1];
else dp[i] = 5 * dp[i-2];
}
for(int i=len1 + 1; i<len2; ++i) res += dp[i];
return res;
}
private:
void dfs1(vector<string>& ss, string s, string p, int &res){
if(s.size() == p.size() && s.compare(p) >= 0) {
if(s.empty() || s.size()<2 || s[0]!='0') ++res;
return;
}
for(int i=0; i<ss.size(); ++i){
if(((int)p.size())&1 && s.empty()) {
if(ss[i].size() == 1) dfs1(ss, s+ss[i], n-1, res);
}
else{
if(ss[i].size()>1) {
dfs1(ss, ss[i].substr(0, 1) + s + ss[i].substr(1), n-2, res);
}
else dfs1(ss, ss[i]+s+ss[i], n-2, res);
}
}
}
void dfs2(vector<string>& ss, string s, string p, int &res){
if(s.size() == p.size() && s.compare(p) <= 0) {
if(s.empty() || s.size()<2 || s[0]!='0') ++res;
return;
}
for(int i=0; i<ss.size(); ++i){
if(((int)p.size())&1 && s.empty()) {
if(ss[i].size()>1) dfs2(ss, s+ss[i], n-1, res);
}
else{
if(ss[i].size()>1) {
dfs2(ss, ss[i].substr(0, 1) + s + ss[i].substr(1), n-2, res);
}
else dfs2(ss, ss[i]+s+ss[i], n-2, res);
}
}
}
bool isValid(string s) {
int i = 0, len = s.size(), j = len - 1;
while(i<=j) {
if(s[i] == s[j]) {
if(s[i] == '0' || s[i] == '1' || s[i] == '8') {
++i;
--j;
}
else return false;
}
else {
if(s[i] == '6' && s[j] == '9' || s[i] == '9' && s[j] == '6') {
++i;
--j;
}
else return false;
}
}
return true;
}
};
Third Solution:
To make the code shorter, we can write a sub-function to calculate the total valid number smaller than a val. Then we just need to call this sub-function twice and calculate the difference.
We still need to figure out whether high itself is valid or not, and it is Srobogrammatic Number I.
See the code below:
Strobogrammatic Number III - LeetCode
class Solution {
public:
int findStrobogrammatic(string low, string high) {
if(low > high) return 0;
int res = 0;
vector<string> ss = {"0", "1", "8", "69", "96"};
int ct1 = dfs(ss, "", low), ct2 = dfs(ss, "", high);
res += ct2 - ct1;
return res + isValid(low) ? 1 : 0;
}
private:
int dfs(vector<string>& ss, string s, string p){
if(s.size() == p.size() && p.compare(s) >= 0) {
if(s.empty() || s.size()<2 || s[0]!='0') return 1;
return 0;
}
int res = 0;
for(int i=0; i<ss.size(); ++i){
if(((int)p.size())&1 && s.empty()) {
if(ss[i].size() == 1) res += 1 + dfs(ss, s+ss[i], n-1, res);
}
else{
if(ss[i].size()>1) {
res += 1 + dfs(ss, ss[i].substr(0, 1) + s + ss[i].substr(1), n-2, res);
}
else res += 1 + dfs(ss, ss[i]+s+ss[i], n-2, res);
}
}
return res;
}
bool isValid(string s) {
int i = 0, len = s.size(), j = len - 1;
while(i<=j) {
if(s[i] == s[j]) {
if(s[i] == '0' || s[i] == '1' || s[i] == '8') {
++i;
--j;
}
else return false;
}
else {
if(s[i] == '6' && s[j] == '9' || s[i] == '9' && s[j] == '6') {
++i;
--j;
}
else return false;
}
}
return true;
}
};
No comments:
Post a Comment