Strobogrammatic Number 2 - Generate for length n

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:

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

Solution

Method 1 - DFS

We can use following approach:

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

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

Java

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