Problem

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.

Examples

Example 1:

Input: low = "50", high = "100"
Output: 3
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Solution

Method 1 - Generate the numbers

We can do it naively using following steps:

  1. Generate - We can use the problem Strobogrammatic Number 2 - Generate for length n ranging from the length of low to the length of high.
  2. Count Valid Numbers - Check each generated strobogrammatic number to see if it falls within the range [low, high].

Code

Java
public class Solution {

	public int strobogrammaticInRange(String low, String high) {
		List<String> ans = new ArrayList<>();

		for (int len = low.length(); len <= high.length(); len++) {
			ans.addAll(helper(len, len));
		}

		int count = 0;

		for (String num: ans) {
			if ((num.length() == low.length() && num.compareTo(low) < 0) ||
				(num.length() == high.length() && num.compareTo(high) > 0)) {
				continue;
			}

			if (!(num.length() > 1 && num.charAt(0) == '0')) { // Skip leading zero numbers
				count++;
			}
		}

		return count;
	}

	private List<String> helper(int n, int m) {
		if (n == 0) return new ArrayList<>(List.of(""));

		if (n == 1) return new ArrayList<>(List.of("0", "1", "8"));

		List<String> list = helper(n - 2, m);
		List<String> result = new ArrayList<>();

		for (String s: list) {
			if (n != m) {
				result.add("0" + s + "0");
			}
			result.add("1" + s + "1");
			result.add("6" + s + "9");
			result.add("8" + s + "8");
			result.add("9" + s + "6");
		}

		return result;
	}

}

Complexity

  • ⏰ Time complexity: O(5^n)
  • 🧺 Space complexity: O(n)