Strobogrammatic Number II

LintCode Q 644 - Strobogrammatic Number II

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.

Strobogrammatic Number (Mirror Number)

Solution

We expanded the target String from center to two sides by recursively calling the helper method.

Code:

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

private List<String> helper(int n, int target) {
	// boundary case
	if (n == 0) return new ArrayList<String>(Arrays.asList(""));
	if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));

	List<String> strs = helper(n - 2, target);
	List<String> res = new ArrayList<>();

	for (String str: strs) {
		if (n != target) res.add('0' + str + '0');
		res.add('1' + str + '1');
		res.add('6' + str + '9');
		res.add('8' + str + '8');
		res.add('9' + str + '6');
	}

	return res;
}