Problem

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

Examples

Example 1:

1
2

Input:  "69"
Output: true

Example 2:

1
2

Input:  "88"
Output: true

Example 3:

1
2

Input:  "962"
Output: false

Solution

Sure! Let’s create a program to find all strobogrammatic numbers with N digits. Strobogrammatic numbers are numbers that look the same when rotated 180 degrees. The pairs of digits that make up strobogrammatic numbers are:

  • 0 and 0
  • 1 and 1
  • 6 and 9
  • 8 and 8
  • 9 and 6

Method 1 - Using Two Pointers and Map

We can create the map of pairs we discussed above. Now, this problem can be considered a special type of palindrome detection or can be solved using double pointers.

  • If the first and last numbers are the same, they must be either 0, 1, or 8.
  • If they differ, then one must be 6 and the other 9, or vice versa.
  • Any other cases will return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
	public boolean isStrobogrammatic(String num) {
		Map<Character, Character> map = Map.of(
			'0', '0',
			'1', '1',
			'8', '8',
			'6', '9',
			'9', '6',
		);
		int n = num.length();
		for (int i = 0; i <= n / 2; i++) {
			if (map.get(num.charAt(i)) != num.charAt(n - i - 1)) {
				return false;
			}
		}
		return true;

	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 1 - Using Two Pointers but no Map

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
	public boolean isStrobogrammatic(String num) {
		if (num == null || num.length() == 0) {
			return true;
		}
		int n = num.length();
		if (n == 1) {
			return num.equals("0") || num.equals("1") || num.equals("8");
		}

		int l = 0, r = n - 1;
		while (l <= r) {
			if (num.charAt(l) == num.charAt(r)) {
				if (num.charAt(l) != '1' && num.charAt(l) != '0' && num.charAt(l) != '8'){
					return false;
				}
			} else {
				if ((num.charAt(l) != '6' || num.charAt(r) != '9') && (num.charAt(l) != '9' || num.charAt(r) != '6')) {
					return false;
				}
			}
			l++; r--;
		}

		return true;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)