Strobogrammatic Number III Solution in C++

Ah, the Strobogrammatic Number III problem! It’s like trying to find a mirror image of a number that’s been through a funhouse. You know, the kind of number that looks the same when flipped upside down? Imagine you’re at a carnival, and you see a number that looks like a 6 when you’re standing normally, but when you flip it, it becomes a 9. It’s all fun and games until you realize you need to count how many of these tricky numbers exist within a certain range.

Problem Description

In this problem, you are tasked with finding how many strobogrammatic numbers exist within a given range defined by two strings, low and high. A strobogrammatic number is one that appears the same when rotated 180 degrees. The digits that can form strobogrammatic pairs are:

0 ↔ 0
1 ↔ 1
6 ↔ 9
8 ↔ 8
9 ↔ 6

So, if you think you can just flip a number upside down and call it a day, think again! You need to ensure that the number falls within the specified range.

Code Solution


class Solution {
 public:
  int strobogrammaticInRange(string low, string high) {
    int ans = 0;

    for (int n = low.length(); n <= high.length(); ++n) {
      string s(n, ' ');
      dfs(low, high, s, 0, n - 1, ans);
    }

    return ans;
  }

 private:
  const vector> pairs{
      {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};

  void dfs(const string& low, const string& high, string& s, int l, int r,
           int& ans) {
    if (l > r) {
      if (s.length() == low.length() && s < low)
        return;
      if (s.length() == high.length() && s > high)
        return;
      ++ans;
      return;
    }

    for (const auto& [leftDigit, rightDigit] : pairs) {
      if (l == r && leftDigit != rightDigit)
        continue;
      s[l] = leftDigit;
      s[r] = rightDigit;
      if (s.length() > 1 && s[0] == '0')
        continue;
      dfs(low, high, s, l + 1, r - 1, ans);
    }
  }
};

Approach

The approach taken in this solution involves a depth-first search (DFS) to generate all possible strobogrammatic numbers of varying lengths. The algorithm starts by iterating through lengths from the length of low to the length of high. For each length, it recursively builds potential strobogrammatic numbers using a helper function (dfs). The function checks if the generated number is within the specified range before counting it.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * 5^(N/2)), where N is the length of the longest number.
Space Complexity	O(N), where N is the length of the number being generated, due to the recursion stack.

Real-World Example

Imagine you’re at a digital clock store, and you want to find out how many different times can be displayed that look the same when viewed upside down. You’d be counting strobogrammatic numbers! Just like how you can’t have a time that starts with a 0 in a 12-hour format, the same rules apply here.