Problem

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

Find all strobogrammatic numbers that are of length = n.

Examples

Example 1:

1
2

Input:  n = 2
Output: ["11","69","88","96"]

Similar Problems

Strobogrammatic Number 1 - Check if strobogrammatic

Solution

Method 1 - DFS

We can use following approach:

  1. Use recursion to generate strobogrammatic numbers by placing strobogrammatic pairs at the start and end of the number.
  2. Handle the base cases where n is 0 or 1.
    1. n == 0 ⇨ empty string
    2. n == 1 ⇨ [0,1,8]
  3. Construct numbers of length n by placing valid strobogrammatic pairs and recursively constructing the inner part of the number.
1
2
3
4
5
6
7

f(n) = [
		("0" + f(n-2) + "0"),
		("1" + f(n-2) + "1"),
		("6" + f(n-2) + "9"),
		("8" + f(n-2) + "8"),
		("9" + f(n-2) + "6"),
	]

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
28
29
30
31
32
33

public class Solution {

	public List<String> findStrobogrammatic(int n) {
		return helper(n, n);
	}

	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> ans = new ArrayList<>();

		for (String s: list) {
			if (n != m) { // as we cannot start with 0
				ans.add("0" + s + "0");
			}

			ans.add("1" + s + "1");
			ans.add("6" + s + "9");
			ans.add("8" + s + "8");
			ans.add("9" + s + "6");
		}

		return result;
	}
}

Complexity

  • ⏰ Time complexity: O(5^(n/2)), each time we generate 5 pairs
  • 🧺 Space complexity: O(n), for using recursion stack