247. Strobogrammatic Number II
Problem Description
The task is to generate all strobogrammatic numbers of a given length n
. A number is considered strobogrammatic if it looks the same when rotated 180 degrees. This means that when you flip the number upside down, it should appear identical to its original appearance. To understand this better, imagine how the numbers would look on a seven-segment display; the numbers 0, 1, and 8 look the same when flipped, while 6 and 9 look like each other when turned upside down.
It's important to note that only the digits 0, 1, 6, 8, and 9 can be used to form strobogrammatic numbers, and when forming numbers of more than 1 digit, the number cannot start with 0 (since that would not be considered a valid number format).
When presented with an integer n
, we are required to return a list of strings, where each string represents a strobogrammatic number of length n
. The ordering of the output numbers is not important, meaning any order in the returned list is acceptable.
Intuition
The solution to this problem can be visualized as a recursive process where we build the strobogrammatic numbers from the inside out. At each step of the recursion, we're focused on adding a layer of digits to the current number.
When the length u
we are building is 0, the base case is reached, and we return an empty list since there can't be a number with zero digits. Similarly, when u
is 1, the possible strobogrammatic numbers are those that consist of only a single digit that looks the same when flipped, namely 0, 1, and 8.
For lengths greater than 1, we need to form numbers by placing strobogrammatic pairs at the beginning and end of the numbers we have formed so far. The pairs are (1, 1), (8, 8), (6, 9), and (9, 6), since these are the digits that maintain their strobogrammatic property when placed on opposite ends.
The recursive function dfs(u)
deals with the construction of these numbers. For any given u
, it reduces the problem to finding strobogrammatic numbers of length u - 2
and adds the strobogrammatic pairs around them, effectively increasing their length by 2.
An additional rule is set for the outermost layer when u
is equal to the original n
. We do not add the pair (0, 0) as that would lead to numbers starting with 0, which is not allowed. So, the 0 + v + 0
combination is only added when we're not at the outermost layer.
Using this recursive strategy, when we reach the full length n
, we will have created all possible combinations of strobogrammatic numbers. The function dfs(n)
initiates this process and the list returned from this function is the final answer.
Learn more about Recursion patterns.
Solution Approach
The provided solution approach uses a depth-first search (DFS) as the primary algorithm for constructing strobogrammatic numbers. It leverages recursion to build the numbers layer by layer, beginning from the middle and expanding outwards. The fundamental data structure used is a list to collect and return the possible strobogrammatic numbers.
Recursive Strategy
The dfs
function is at the core of the strategy and is recursive in nature. The parameter u
indicates the current length of the strobogrammatic number being built.
-
Base Cases:
- When
u
equals 0, the function returns a list containing an empty string['']
, which symbolically represents the middle of the strobogrammatic number. - When
u
equals 1, the function returns the list['0', '1', '8']
, as these are the only digits that remain unchanged when rotated 180 degrees individually.
- When
-
Recursive Step: For any
u
greater than 1,dfs(u)
calls itself withu - 2
, aiming to get the strobogrammatic numbers of a smaller length that will form the middle part of the new, larger numbers.During the recursive step, the function iterates over each string
v
returned by thedfs(u - 2)
call. It then adds each strobogrammatic pair('11', '88', '69', '96')
aroundv
to theans
list, thus forming a new, longer strobogrammatic number. This process is how the solution builds the numbers from the inside out.The condition
if u != n
ensures that we do not add the pair '00' at the outermost layer when constructing numbers of lengthn
. Zeros are added in the middle layers because they are allowed there but not as the leading digit of the entire number. -
Efficient Construction: By using the above pairs and ensuring that '0' is not added as the outermost digits, the algorithm efficiently constructs the correct strobogrammatic numbers while maintaining the necessary constraints.
Backtracking
A subtle form of backtracking is exhibited in this DFS function. When the function appends a new pair to a smaller strobogrammatic number, it explores that path entirely, and upon completion, it backtracks to try the next pair. This way, it explores all possible number formations of length n
.
Conclusion
The recursive building process and intelligent pair placement combine to ensure each constructed number is strobogrammatic. This approach is effective because it expands upon smaller already-valid numbers, ensuring that the overall structure of the number retains the strobogrammatic property.
Once the recursion unwinds back to the initial call with dfs(n)
, all strobogrammatic numbers of length n
are returned, thus solving the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we want to find all strobogrammatic numbers of length n = 2
. We can execute the solution approach to see how it works.
- We call the recursive function
dfs(2)
. - Since
u = 2
is not equal to 0 or 1, we proceed with the recursive step and calldfs(0)
to find strobogrammatic numbers of lengthu - 2
. dfs(0)
returns['']
since the base caseu = 0
simply means the middle of the strobogrammatic number, which is the empty string in this case.- Now, with
u = 2
, we need to surround this empty string with strobogrammatic pairs to form numbers of length 2. - We iterate through each strobogrammatic pair ('11', '88', '69', '96') and surround the string from
dfs(0)
, which is the middle part. We don't add '00' becauseu = n
and we can't start with a zero.- Add '11' to the empty string:
1
+ '' +1
=11
- Add '88' to the empty string:
8
+ '' +8
=88
- Add '69' to the empty string:
6
+ '' +9
=69
- Add '96' to the empty string:
9
+ '' +6
=96
- Add '11' to the empty string:
- The
ans
list is now['11', '88', '69', '96']
. - Since we are now done with adding pairs to the length 2 strobogrammatic number and
u = n
, we conclude the function and return['11', '88', '69', '96']
as the final result.
As we can see from this example, the recursive function builds the strobogrammatic numbers from the center outwards, and only pairs that satisfy the strobogrammatic property are added in each step. For numbers with lengths greater than 2, this process continues inward, building up from shorter strobogrammatic strings to the desired length.
This walkthrough exemplifies the mechanics of the provided recursive DFS solution in constructing valid strobogrammatic numbers of a specified length.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findStrobogrammatic(self, n: int) -> List[str]:
5 # Helper function to perform depth-first search.
6 def dfs(depth):
7 # Base case for recursion: when no more characters can be placed.
8 if depth == 0:
9 return ['']
10 # When we have space for one character, only 0, 1, and 8 are strobogrammatic by themselves.
11 if depth == 1:
12 return ['0', '1', '8']
13
14 # Recurse with two fewer spaces to place the rest.
15 subresults = dfs(depth - 2)
16 full_results = []
17 # Iterate through each subresult from the recursive call.
18 for subresult in subresults:
19 # Add strobogrammatic pairs around the subresult.
20 for left, right in ('11', '88', '69', '96'):
21 full_results.append(left + subresult + right)
22 # If we are not at the outermost layer, we can use '0' as a strobogrammatic pair as well.
23 if depth != n:
24 full_results.append('0' + subresult + '0')
25 return full_results
26
27 # Start the recursion with the full length n.
28 return dfs(n)
29
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Collections;
4import java.util.List;
5
6class Solution {
7 // Pairs of digits that are strobogrammatic, i.e. they look the same when rotated 180 degrees
8 private static final int[][] STROBOGRAMMATIC_PAIRS = {{1, 1}, {8, 8}, {6, 9}, {9, 6}};
9 private int n;
10
11 // Main method to find all strobogrammatic numbers of length n
12 public List<String> findStrobogrammatic(int n) {
13 this.n = n;
14 return buildStrobogrammaticNumbers(n);
15 }
16
17 // Helper method to recursively build strobogrammatic numbers of the current length
18 private List<String> buildStrobogrammaticNumbers(int currentLength) {
19 // Base case for recursion: If current length is 0, return a list with an empty string
20 if (currentLength == 0) {
21 return Collections.singletonList("");
22 }
23
24 // Base case for length 1: Only digits 0, 1, and 8 are strobogrammatic, return them as strings
25 if (currentLength == 1) {
26 return Arrays.asList("0", "1", "8");
27 }
28
29 // List to store the strobogrammatic numbers of the current call
30 List<String> strobogrammaticNumbers = new ArrayList<>();
31
32 // Get the strobogrammatic numbers for (currentLength - 2)
33 List<String> subNumbers = buildStrobogrammaticNumbers(currentLength - 2);
34
35 // Loop over each strobogrammatic number of smaller length
36 for (String number : subNumbers) {
37 for (int[] pair : STROBOGRAMMATIC_PAIRS) { // Loop over each strobogrammatic pair
38 // Surround the smaller-length number with a strobogrammatic pair
39 strobogrammaticNumbers.add(pair[0] + number + pair[1]);
40 }
41
42 // If we are not building the outermost layer, add '0's to the list as well
43 // This is because '0's cannot be at the beginning and end of a strobogrammatic number
44 if (currentLength != n) {
45 strobogrammaticNumbers.add("0" + number + "0");
46 }
47 }
48 return strobogrammaticNumbers;
49 }
50}
51
1#include <vector>
2#include <string>
3#include <functional>
4using namespace std;
5
6class Solution {
7public:
8 // Define pairs of strobogrammatic numbers where each pair is symmetrical around the vertical axis.
9 const vector<pair<char, char>> kPairs = {{'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
10
11 // Main method to find all strobogrammatic numbers of length n.
12 vector<string> findStrobogrammatic(int n) {
13 // Define a recursive function using lambda that takes the length of the number to be constructed.
14 function<vector<string>(int)> dfs = [&](int length) {
15 // Base case for recursion: when the length is 0, return an empty string.
16 if (length == 0) return vector<string>{""};
17 // If the length is 1, the strobogrammatic numbers can only be one of these characters.
18 if (length == 1) return vector<string>{"0", "1", "8"};
19
20 // Recursive call, which reduces the length of the number by two.
21 vector<string> ans; // This will store the resulting strobogrammatic numbers.
22 for (auto &v : dfs(length - 2)) {
23 // Add each pair of numbers to both ends of each string returned for length-2.
24 for (auto &[left, right] : kPairs) ans.push_back(left + v + right);
25 // If we are not at the outermost level of the original number, add '0' to both ends as well.
26 // '0' cannot be at the beginning or end of the number, hence it is only added when length != n.
27 if (length != n) ans.push_back('0' + v + '0');
28 }
29 // Return the constructed list of strobogrammatic numbers.
30 return ans;
31 };
32
33 // Start the recursive function with the initial length n.
34 return dfs(n);
35 }
36};
37
1// Import the necessary modules for utility functions
2import { Vector, Pair } from './path_to_utility'; // Replace with the correct path to utility modules if available
3
4// Define pairs of strobogrammatic numbers where each pair is symmetrical around the vertical axis.
5const kPairs: Array<Pair<char, char>> = [['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']];
6
7// Define a recursive function using lambda that takes the length of the number to be constructed.
8const findStrobogrammaticNumbers = (length: number, initialLength: number): Array<string> => {
9 // Base case for recursion: when the length is 0, return an empty string.
10 if (length === 0) return [''];
11 // If the length is 1, the strobogrammatic numbers can only be one of these characters.
12 if (length === 1) return ['0', '1', '8'];
13
14 // Recursive call, which reduces the length of the number by two.
15 const results: Array<string> = [];
16 for (const v of findStrobogrammaticNumbers(length - 2, initialLength)) {
17 // Add each pair of numbers to both ends of each string returned for length-2.
18 for (const [left, right] of kPairs) results.push(left + v + right);
19 // If we are not at the outermost level of the original number, add '0' to both ends as well.
20 // '0' cannot be at the beginning or end of the number, hence it is only added when length != initialLength.
21 if (length !== initialLength) results.push('0' + v + '0');
22 }
23 // Return the constructed list of strobogrammatic numbers.
24 return results;
25};
26
27// Main method to find all strobogrammatic numbers of length n.
28const findStrobogrammatic = (n: number): Array<string> => {
29 // Start the recursive function with the initial length n.
30 return findStrobogrammaticNumbers(n, n);
31};
32
33// Note that helper types like Pair and Vector are not native TypeScript types and would typically not be necessary.
34// They are used here as stand-ins for whatever utility types you have to represent a pair and a list.
35// If those utilities are not available, TypeScript's native types (e.g., tuples and arrays) can directly be used.
36
Time and Space Complexity
The given Python code generates all strobogrammatic numbers of length n
. Here is an analysis of its time complexity and space complexity:
-
Time Complexity:
We can analyze the time complexity by considering the number of recursive calls and the work done in each call. The
dfs
function is called recursively with an argument reduced by 2 in each call until it reaches 0 or 1.For each recursive call to
dfs(u - 2)
, we iterate over the results and append four different pairs to each of the strings (three pairs ifu
is the originaln
to avoid leading zeros). The number of such string concatenations doubles with every additional recursive pair ('00'
,'11'
,'88'
,'69'
,'96'
), minus the case'00'
at the top level to prevent leading zeros in the final numbers.If we start with
n = 0
orn = 1
, the function ends after one call. However, forn > 1
, every two levels of the recursion approximately double the results.Therefore, the time complexity can be approximated as
O(5^(n/2))
. -
Space Complexity:
Space complexity is driven by two factors: the space to store the intermediate results and the depth of the recursive call stack.
For the intermediate results, the maximum space is used when the final list of strobogrammatic numbers is generated. Similar to time complexity, the space usage doubles for every additional level. Since we are generating all possible combinations, the space used to store these combinations will be proportional to the number of combinations, which is
O(5^(n/2))
.Meanwhile, the recursive call stack will have a depth of at most
n/2
(since we reducen
by 2 with each recursive call). Each recursive call requires a constant amount of space, so the total space used by the call stack will beO(n)
.Thus, when accounting for both factors, the space complexity is dominated by the storage for the list of strobogrammatic numbers. Hence, the space complexity is
O(5^(n/2))
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.