Strobogrammatic Number II
Medium · Backtracking · Array · String · Recursion
Problem
A strobogrammatic number looks the same after a 180-degree rotation. Only five digits survive the rotation: 0, 1 and 8 stay themselves, while 6 and 9 turn into each other. So 69, 88 and 818 are strobogrammatic, and 62 is not.
Given an integer n, return every strobogrammatic number with exactly n digits, as strings, in any order. A number with more than one digit never starts with 0.
Examples
Input: n = 2 Output: ["11","69","88","96"]
00 is left out because of its leading zero.
Input: n = 1 Output: ["0","1","8"]
A single digit must rotate into itself, so 6 and 9 do not count.
Input: n = 3 Output: ["101","111","181","609","619","689","808","818","888","906","916","986"]
Four outer pairs around three possible middles.
Constraints
- 1 <= n <= 14
Approaches
- Every rotatable string, then check it — time O(n · 5^n), space O(n · 5^(n/2))
Follow-up
The count alone needs no list: the outer pair has 4 choices, every inner pair 5, and an odd middle 3, so there are 4 · 5^(n/2 - 1) numbers of even length n >= 2 (times 3 when n is odd). Strobogrammatic Number III turns the same idea into counting a range.
Related problems
Start free on Cariara · Coding problems · System design studio
