Strobogrammatic Number II
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(10^n · n)Every n-digit number is generated and checked in O(n).O(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.
- Let lo = 0 if n == 1, otherwise 10^(n-1); let hi = 10^n - 1.
- For each x from lo to hi, write it as a string s.
- 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.
- 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;
}
}class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
rot = "01....9.86"
lo = 0 if n == 1 else 10 ** (n - 1)
hi = 10 ** n - 1
result = []
for x in range(lo, hi + 1):
s = str(x)
i, j = 0, len(s) - 1
ok = True
while i <= j:
if rot[ord(s[i]) - 48] != s[j]:
ok = False
break
i += 1
j -= 1
if ok:
result.append(s)
return resultclass Solution {
public:
vector<string> findStrobogrammatic(int n) {
vector<string> result;
long long lo = 1, hi;
for (int i = 1; i < n; i++) lo *= 10;
hi = lo * 10 - 1;
if (n == 1) lo = 0;
for (long long x = lo; x <= hi; x++) {
string s = to_string(x);
if (isStrobogrammatic(s)) result.push_back(s);
}
return result;
}
private:
bool isStrobogrammatic(const string& s) {
const string rot = "01....9.86";
for (int i = 0, j = (int)s.size() - 1; i <= j; i++, j--) {
if (rot[s[i] - '0'] != s[j]) return false;
}
return true;
}
};function findStrobogrammatic(n) {
const rot = "01....9.86";
const lo = n === 1 ? 0 : 10 ** (n - 1);
const hi = 10 ** n - 1;
const result = [];
for (let x = lo; x <= hi; x++) {
const s = String(x);
let ok = true;
for (let i = 0, j = s.length - 1; i <= j; i++, j--) {
if (rot[s.charCodeAt(i) - 48] !== s[j]) {
ok = false;
break;
}
}
if (ok) result.push(s);
}
return result;
}2Optimal (build from the middle out)
O(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).O(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.
- build(len): if len == 0 return [""]; if len == 1 return ["0", "1", "8"].
- Get inner = build(len - 2).
- For each core in inner and each pair (a, b), add a + core + b, but skip a = '0' when len == n.
- 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;
}
}class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
pairs = [("0", "0"), ("1", "1"), ("6", "9"), ("8", "8"), ("9", "6")]
def build(length: int) -> List[str]:
if length == 0:
return [""]
if length == 1:
return ["0", "1", "8"]
inner = build(length - 2)
result = []
for core in inner:
for a, b in pairs:
if length == n and a == "0":
continue
result.append(a + core + b)
return result
return build(n)class Solution {
public:
vector<string> findStrobogrammatic(int n) {
return build(n, n);
}
private:
vector<string> build(int len, int n) {
if (len == 0) return {""};
if (len == 1) return {"0", "1", "8"};
static const char pairs[5][2] = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
vector<string> inner = build(len - 2, n);
vector<string> result;
for (const string& core : inner) {
for (const auto& p : pairs) {
if (len == n && p[0] == '0') continue;
result.push_back(string(1, p[0]) + core + p[1]);
}
}
return result;
}
};function findStrobogrammatic(n) {
const pairs = [["0", "0"], ["1", "1"], ["6", "9"], ["8", "8"], ["9", "6"]];
const build = (len) => {
if (len === 0) return [""];
if (len === 1) return ["0", "1", "8"];
const inner = build(len - 2);
const result = [];
for (const core of inner) {
for (const [a, b] of pairs) {
if (len === n && a === "0") continue;
result.push(a + core + b);
}
}
return result;
};
return build(n);
}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).