Strobogrammatic Number II

Medium Recursion & Backtracking Choice per Position Original on LeetCode

Reported atGoogle

Strobogrammatic Number II is a medium recursion & backtracking problem solved with the choice per position pattern. The best approach, optimal (build from the middle out), runs in O(n · 5^(n/2)) time and O(n · 5^(n/2)) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every n-digit number) up.

Problem

A strobogrammatic number reads the same after it is rotated by 180 degrees (turned upside down). Under a half turn 0, 1 and 8 stay the same, 6 becomes 9 and 9 becomes 6; every other digit stops being a digit.

Given an integer n, return every strobogrammatic number that has exactly n digits, as strings, in any order. A number with more than one digit may not start with 0.

Examples

Example 1

Input
n = 1
Output
["0", "1", "8"]
Why
Only 0, 1 and 8 look the same after a half turn when they stand alone.

Example 2

Input
n = 3
Output
["101", "111", "181", "609", "619", "689", "808", "818", "888", "906", "916", "986"]
Why
The outer pair is 1-1, 6-9, 8-8 or 9-6, and the middle digit must be 0, 1 or 8: 4 x 3 = 12 numbers.

Constraints

  • 1 <= n <= 14
  • The answer may be returned in any order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 6 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (check every n-digit number)O(10^n · n)O(n) besides the output
Optimal (build from the middle out)O(n · 5^(n/2))O(n · 5^(n/2))

1Brute force (check every n-digit number)

TimeO(10^n · n)Every n-digit number is generated and checked in O(n).
SpaceO(n) besides the outputOnly the current string is held apart from the answer list.

Walk through every number with exactly n digits and keep the ones that read the same after a half turn. Simple, but the count of candidates is 10^n.

  1. Let lo = 0 if n == 1, otherwise 10^(n-1); let hi = 10^n - 1.
  2. For each x from lo to hi, write it as a string s.
  3. Check with two pointers i, j that rotate(s[i]) == s[j] for all i <= j, where rotate is undefined for 2, 3, 4, 5, 7.
  4. Keep s if the check passes.
class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        long lo = n == 1 ? 0 : (long) Math.pow(10, n - 1);
        long hi = (long) Math.pow(10, n) - 1;
        for (long x = lo; x <= hi; x++) {
            String s = Long.toString(x);
            if (isStrobogrammatic(s)) result.add(s);
        }
        return result;
    }

    private boolean isStrobogrammatic(String s) {
        String rot = "01....9.86";
        for (int i = 0, j = s.length() - 1; i <= j; i++, j--) {
            if (rot.charAt(s.charAt(i) - '0') != s.charAt(j)) return false;
        }
        return true;
    }
}

2Optimal (build from the middle out)

TimeO(n · 5^(n/2))There are about 4 · 5^(n/2 - 1) answers and each string of length n is built once (the inner levels are smaller).
SpaceO(n · 5^(n/2))The answer list itself plus the lists of the inner levels.

A valid number of length n is a valid core of length n - 2 wrapped in one of the pairs 0-0, 1-1, 6-9, 8-8, 9-6. Recurse down to length 0 (the empty string) or 1 ("0", "1", "8") and wrap on the way back. The 0-0 pair is skipped only for the outermost layer, so no answer gets a leading zero. Only valid numbers are ever produced.

  1. build(len): if len == 0 return [""]; if len == 1 return ["0", "1", "8"].
  2. Get inner = build(len - 2).
  3. For each core in inner and each pair (a, b), add a + core + b, but skip a = '0' when len == n.
  4. Return build(n).
class Solution {
    private static final char[][] PAIRS = {
        { '0', '0' }, { '1', '1' }, { '6', '9' }, { '8', '8' }, { '9', '6' }
    };

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

    private List<String> build(int len, int n) {
        if (len == 0) return new ArrayList<>(List.of(""));
        if (len == 1) return new ArrayList<>(List.of("0", "1", "8"));
        List<String> inner = build(len - 2, n);
        List<String> result = new ArrayList<>();
        for (String core : inner) {
            for (char[] p : PAIRS) {
                if (len == n && p[0] == '0') continue;
                result.add(p[0] + core + p[1]);
            }
        }
        return result;
    }
}

Edge cases to test

  • n = 1, where the single middle digit may be 0
  • n = 2, where 00 is not allowed because of the leading zero
  • Odd n, which needs a self-symmetric middle digit (0, 1 or 8)

Hints

Hint 1

A half turn reverses the order of the digits and maps 0->0, 1->1, 6->9, 8->8, 9->6. Any other digit makes the number invalid.

Hint 2

So the number is fixed by its outer half: choose matching pairs from the outside in.

Hint 3

Build the length-n answers from the length n - 2 answers by wrapping each one in a pair. Skip the 0...0 wrap only at the outermost level.

FAQ

What is the best time complexity for Strobogrammatic Number II?

Optimal (build from the middle out) runs in O(n · 5^(n/2)) time and O(n · 5^(n/2)) extra space. There are about 4 · 5^(n/2 - 1) answers and each string of length n is built once (the inner levels are smaller).

Which pattern does Strobogrammatic Number II use?

It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Palindrome Partitioning.

Is there a brute force solution for Strobogrammatic Number II?

Yes. Brute force (check every n-digit number) takes O(10^n · n) time and O(n) besides the output space. Walk through every number with exactly n digits and keep the ones that read the same after a half turn.

Which edge cases should I test for Strobogrammatic Number II?

n = 1, where the single middle digit may be 0; n = 2, where 00 is not allowed because of the leading zero; Odd n, which needs a self-symmetric middle digit (0, 1 or 8).