247. Strobogrammatic Number II
Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (viewed upside down).
Example 1:
Input: n = 2
Output: ["11", "69", "88", "96"]
Example 2:
Input: n = 1
Output: ["0", "1", "8"]
Constraints:
1 <= n <= 14
Approach 1: Recursion
To solve this problem, let's explore some sample cases to establish a pattern:
For length 1:
The digits that remain the same or transform into each other after a 180° rotation are '0', '1', '8', '6', and '9'. For a 1-digit number, valid strobogrammatic numbers are '0', '1', and '8'.
For length 2:
We have two positions (indices 0 and 1) which will interchange. We can form valid numbers using the following combinations:
- Two same digits: '11', '88'
- Digits that change into one another: '69', '96'
For length 3:
We have three positions (indices 0, 1, and 2). Here, index 0 and index 2 interchange, but index 1 remains in the same place. We use the 1-digit strobogrammatic numbers to construct 3-digit numbers:
- '0' + (1-digit strobogrammatic numbers) + '0': '101', '181', '808'
- '1' + (1-digit strobogrammatic numbers) + '1': '101', '111', '181'
- '6' + (1-digit strobogrammatic numbers) + '9': '609', '619', '689'
- '8' + (1-digit strobogrammatic numbers) + '8': '808', '818', '888'
- '9' + (1-digit strobogrammatic numbers) + '6': '906', '916', '986'
For length 4:
We have four positions (indices 0, 1, 2, and 3). The valid numbers are constructed by appending reversible digits to both ends of 2-digit strobogrammatic numbers:
- '1' + (2-digit strobogrammatic numbers) + '1': '1001', '1111', '1691', '1881', '1961'
- '6' + (2-digit strobogrammatic numbers) + '9': '6009', '6119', '6699', '6889', '6969'
- '8' + (2-digit strobogrammatic numbers) + '8': '8008', '8118', '8698', '8888', '8968'
- '9' + (2-digit strobogrammatic numbers) + '6': '9006', '9116', '9696', '9886', '9966'
To find all strobogrammatic numbers of length N, we can use recursion. We first find all strobogrammatic numbers of length N - 2 and then append reversible digits to the beginning and end.
Algorithm:
- Initialize a data structure
reversiblePairswith all pairs of reversible digits. - Call the recursive function
generateStroboNumbers(n, finalLength), wherenis the current length andfinalLengthis the length of the final strobogrammatic numbers. - In
generateStroboNumbers(n, finalLength):- Check base cases: if
n == 0, return [""]; ifn == 1, return ["0", "1", "8"]. - Recursively generate strobogrammatic numbers of length
n - 2and store them insubAns. - Initialize an empty array
currStroboNumsto store numbers of lengthn. - For each number in
subAns, append each reversible pair to the beginning and end, except when appending '00' andn == finalLength(as '00' cannot be at the beginning). - Return
currStroboNumscontaining all strobogrammatic numbers of lengthn.
- Check base cases: if
class Solution {
public char[][] reversiblePairs = {
{'0', '0'}, {'1', '1'},
{'6', '9'}, {'8', '8'}, {'9', '6'}
};
public List generateStroboNumbers(int n, int finalLength) {
if (n == 0) {
// 0-digit strobogrammatic number is an empty string.
return new ArrayList<>(List.of(""));
}
if (n == 1) {
// 1-digit strobogrammatic numbers.
return new ArrayList<>(List.of("0", "1", "8"));
}
List prevStroboNums = generateStroboNumbers(n - 2, finalLength);
List currStroboNums = new ArrayList<>();
for (String prevStroboNum : prevStroboNums) {
for (char[] pair : reversiblePairs) {
// We can only append 0's if it is not first digit.
if (pair[0] != '0' || n != finalLength) {
currStroboNums.add(pair[0] + prevStroboNum + pair[1]);
}
}
}
return currStroboNums;
}
public List findStrobogrammatic(int n) {
return generateStroboNumbers(n, n);
}
}
Complexity Analysis
Here, N is the length of the strobogrammatic numbers we need to find.
To understand the complexity, let's visualize the recursion tree:
Our recursive function calls itself with N - 2 at each level. This forms an arithmetic progression (AP) series:
[N, N-2, N-4, ..., 0].
The number of levels in the recursion tree is at most N / 2.
Time Complexity:
The time complexity can be approximated as N ⋅ 5⌊N/2⌋ + 1.
At each recursive level, we iterate over all strings from the previous level and append 5 pairs of characters to each string. Thus, the size of the currStroboNums array increases by a factor of 5 at each level, except for the last level where it increases by a factor of 4 (since '00' is omitted).
- For even N, the total number of iterations is approximately 5 + 52 + 53 + ... + 5(N/2)-1 + 4 ⋅ 5(N/2)-1.
- For odd N, the total number of iterations is approximately 3 ⋅ 5 + 3 ⋅ 52 + 3 ⋅ 53 + ... + 3 ⋅ 5(N-3)/2 + 3 ⋅ 4 ⋅ 5(N-3)/2.
Space Complexity:
The space complexity is O(N ⋅ 5⌊N/2⌋).
We make at most N / 2 recursive calls, so the call stack uses O(N / 2) space.
The currStroboNums array is the output, and in the final recursion, it is not considered auxiliary space. However, in earlier recursions, currStroboNums is considered auxiliary space. We store at most (N/2) - 1 strings when N is even, or approximately 3 ⋅ 5(N-1)/2 - 1 when N is odd, and each string has a length of N - 2.
Thus, the overall space used is approximately (N - 2) ⋅ 5⌊N/2⌋ + N / 2 ≈ N ⋅ 5⌊N/2⌋.
