Skip to main content

247. Strobogrammatic Number II

medium

Generate all strobogrammatic numbers of length n — numbers that look the same when rotated 180 degrees. The recursion builds outward from the center, two characters at a time, restricting choices to the strobogrammatic digit set.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Constraints

  • 1 <= n <= 14

Examples

Example 1

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

Example 2

Input
n = 1
Output
["0","1","8"]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Strobogrammatic digit pairs: (0,0), (1,1), (6,9), (8,8), (9,6). Singletons: 0, 1, 8.

Hint 2

Recurse on a target inner length and the outer length. helper(k) returns all strobogrammatic strings of length k.

Hint 3

Base cases: k == 0 -> [""], k == 1 -> ["0", "1", "8"].

Hint 4

Recursive: for each inner string from helper(k - 2), wrap it with each pair. Skip outer (0, 0) when this isn't the innermost recursion (no leading zeros).

Solution approach

Reveal approach

Recurse on length: helper(k, isOuter). Base cases: k == 0 -> return [""]; k == 1 -> return ["0", "1", "8"]. Recursive: get inner strings from helper(k - 2, false), then for each pair in [('0','0'),('1','1'),('6','9'),('8','8'),('9','6')], if isOuter and pair == ('0','0'), skip (no leading zero in the final answer). Otherwise wrap inner with pair: pair[0] + inner + pair[1]. Top-level call: helper(n, true). Time and space are O(5^(n/2) * n) — the number of valid strobogrammatic numbers grows exponentially in n/2.

Complexity

Time
O(5^(n/2) * n)
Space
O(5^(n/2) * n)

Related patterns

  • recursion
  • build-from-center

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Meta

More Recursion practice problems

See all Recursion problems →