class Solution:
def findStrobogrammatic(self, n: int) -> list:
def build(n, total_length):
if n == 0: return [""]
if n == 1: return ["0", "1", "8"]
middles = build(n-2, total_length)
result = []
for middle in middles:
if n != total_length:
result.append("0" + middle + "0")
result.append("1" + middle + "1")
result.append("6" + middle + "9")
result.append("8" + middle + "8")
result.append("9" + middle + "6")
return result
return build(n, n)
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
return build(n, n);
}
private:
vector<string> build(int n, int total) {
if (n == 0) return {""};
if (n == 1) return {"0", "1", "8"};
vector<string> middles = build(n-2, total);
vector<string> res;
for (const string& middle : middles) {
if (n != total) res.push_back("0" + middle + "0");
res.push_back("1" + middle + "1");
res.push_back("6" + middle + "9");
res.push_back("8" + middle + "8");
res.push_back("9" + middle + "6");
}
return res;
}
};
class Solution {
public List<String> findStrobogrammatic(int n) {
return build(n, n);
}
private List<String> build(int n, int total) {
if (n == 0) return Arrays.asList("");
if (n == 1) return Arrays.asList("0", "1", "8");
List<String> middles = build(n-2, total);
List<String> res = new ArrayList<>();
for (String middle : middles) {
if (n != total) res.add("0" + middle + "0");
res.add("1" + middle + "1");
res.add("6" + middle + "9");
res.add("8" + middle + "8");
res.add("9" + middle + "6");
}
return res;
}
}
var findStrobogrammatic = function(n) {
function build(n, total) {
if (n === 0) return [""];
if (n === 1) return ["0", "1", "8"];
let middles = build(n - 2, total);
let res = [];
for (let middle of middles) {
if (n !== total) res.push("0" + middle + "0");
res.push("1" + middle + "1");
res.push("6" + middle + "9");
res.push("8" + middle + "8");
res.push("9" + middle + "6");
}
return res;
}
return build(n, n);
};
Given an integer n, generate all strobogrammatic numbers of length n.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
The digits allowed for strobogrammatic numbers are: 0, 1, 6, 8, 9. When rotated:
0 becomes 01 becomes 16 becomes 98 becomes 89 becomes 6
The task is to return all possible strobogrammatic numbers of length n as a list of strings. Leading zeros are not allowed unless the number itself is "0".
At first glance, one might consider generating all numbers of length n and checking if each is strobogrammatic. However, this brute-force method is inefficient, especially as n increases, because the number of possible numbers grows exponentially.
Instead, we can take advantage of the properties of strobogrammatic numbers. For a number to be strobogrammatic, its digits must form valid strobogrammatic pairs from the outside in. This means the first and last digit must be a valid pair (like 1 and 1, or 6 and 9), the second and second-to-last must be a valid pair, and so on. For odd-length numbers, the middle digit must be one that is itself strobogrammatic (0, 1, or 8).
This insight suggests a recursive or backtracking approach, building numbers from the outside in, only using valid pairs at each step.
To efficiently generate all strobogrammatic numbers of length n, we use a recursive approach:
n == 0, return a list with an empty string (for building even-length numbers).n == 1, return a list with the digits ["0", "1", "8"] (the only valid single-digit strobogrammatic numbers).n-2 (the "middles").n.("0", "0"), ("1", "1"), ("6", "9"), ("8", "8"), ("9", "6").("0", "0") as the outermost pair (to avoid leading zeros), except when building the innermost part of the number.n.This approach ensures we only generate valid strobogrammatic numbers, avoiding unnecessary computation and invalid cases.
Let's walk through the process for n = 2:
n = 0 returns [""].
n = 2, we take each "middle" from [""] and wrap it with each valid pair:
("0", "0"): Yields "00" (but we skip this, since leading zeros are not allowed for numbers longer than 1 digit).("1", "1"): Yields "11"("6", "9"): Yields "69"("8", "8"): Yields "88"("9", "6"): Yields "96"["11", "69", "88", "96"].
For n = 3:
n = 1 returns ["0", "1", "8"].
("0","0") at the outermost level):
"0": "101", "609", "808", "906""1": "111", "619", "818", "916""8": "181", "689", "888", "986"["101", "609", "808", "906", "111", "619", "818", "916", "181", "689", "888", "986"].
Brute-force approach: Generating all numbers of length n and checking each for strobogrammatic property would take O(10^n) time and space, which is infeasible for large n.
Optimized recursive approach: At each level, we build numbers by adding valid pairs, and the total number of strobogrammatic numbers of length n is approximately O(5^{n/2}) (since there are 5 valid pairs and we add pairs from the outside in). The time and space complexity is thus O(5^{n/2}), which is much more efficient than brute-force.
Each number is constructed only once, and we avoid generating invalid numbers with leading zeros.
The strobogrammatic number generation problem is elegantly solved using a recursive, build-from-the-outside-in approach. By leveraging the symmetry and digit-pairing rules, we avoid brute-force enumeration and efficiently generate only valid numbers. The key insight is to recursively construct smaller strobogrammatic numbers and wrap them with valid digit pairs, skipping leading zeros where necessary. This results in a clean, efficient, and scalable solution.