Strobogrammatic Number III Solution in Java

Ah, the Strobogrammatic Number III problem! It’s like trying to find a mirror image of a number that’s not just a reflection but also a bit of a trickster. Imagine you’re at a carnival, and you see a funhouse mirror that makes you look all wobbly and weird. That’s what strobogrammatic numbers are like—numbers that look the same when rotated 180 degrees.

Now, if you’re wondering why anyone would care about such numbers, think of it this way: you’re trying to impress your friends with your knowledge of quirky numbers at a party. “Did you know that 69 and 88 are strobogrammatic?” you say, and suddenly you’re the life of the party. Or maybe not. But hey, at least you tried!

Problem Description

The task is to count how many strobogrammatic numbers exist within a given range [low, high]. A strobogrammatic number is one that appears the same when rotated 180 degrees. For example, “69”, “88”, and “818” are strobogrammatic, while “123” is not.

Solution Links

Code Solution


class Solution {
  public int strobogrammaticInRange(String low, String high) {
    for (int n = low.length(); n <= high.length(); ++n) {
      char[] c = new char[n];
      dfs(low, high, c, 0, n - 1);
    }
    return ans;
  }

  private int ans = 0;

  private static final char[][] pairs = {
      {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};

  private void dfs(final String low, final String high, char[] c, int l, int r) {
    if (l > r) {
      final String s = new String(c);
      if (s.length() == low.length() && s.compareTo(low) < 0)
        return;
      if (s.length() == high.length() && s.compareTo(high) > 0)
        return;
      ++ans;
      return;
    }

    for (char[] pair : pairs) {
      if (l == r && pair[0] != pair[1])
        continue;
      c[l] = pair[0];
      c[r] = pair[1];
      if (c.length > 1 && c[0] == '0')
        continue;
      dfs(low, high, c, l + 1, r - 1);
    }
  }
}

Approach Explanation

The approach used in this solution is a depth-first search (DFS) to generate all possible strobogrammatic numbers of varying lengths. The algorithm iterates through lengths from the length of low to the length of high, constructing potential strobogrammatic numbers character by character. It checks if the generated number falls 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 in the range.
Space Complexity	O(N), where N is the length of the number being constructed.

Real-World Example

Imagine you’re designing a digital clock that can only display strobogrammatic numbers. You want to know how many valid times can be displayed between 00:00 and 23:59. This problem is akin to counting those valid times, ensuring they look the same when viewed upside down.