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.

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.
  • Recursive Step: For any u greater than 1, dfs(u) calls itself with u - 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 the dfs(u - 2) call. It then adds each strobogrammatic pair ('11', '88', '69', '96') around v to the ans 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 length n. 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.

💪
Level Up Your
Algo Skills

Example 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.

  1. We call the recursive function dfs(2).
  2. Since u = 2 is not equal to 0 or 1, we proceed with the recursive step and call dfs(0) to find strobogrammatic numbers of length u - 2.
  3. dfs(0) returns [''] since the base case u = 0 simply means the middle of the strobogrammatic number, which is the empty string in this case.
  4. Now, with u = 2, we need to surround this empty string with strobogrammatic pairs to form numbers of length 2.
  5. 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' because u = 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
  6. The ans list is now ['11', '88', '69', '96'].
  7. 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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 if u is the original n 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 or n = 1, the function ends after one call. However, for n > 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 reduce n 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 be O(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)).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫