Strobogrammatic Number II
To find all strobogrammatic numbers of length n
, we can build the numbers recursively, using the strobogrammatic pairs '0'
and '0'
, '1'
and '1'
, '6'
and '9'
, '8'
and '8'
, '9'
and '6'
. However, we should avoid using '0'
at the beginning and end of the numbers.
Here’s the code:
|
|
The function helper
recursively constructs the strobogrammatic numbers. It is called with two parameters n
and m
, where n
is the current length for which the strobogrammatic numbers are being generated, and m
is the original length.
Here’s how it works:
- Base cases: If
n
is 0, it returns an empty string. Ifn
is 1, it returns the strobogrammatic numbers of length 1. - Recursively calls
helper
forn-2
and builds the strobogrammatic numbers of lengthn
based on that. - Skips adding “0” at the beginning and end if
n
is equal tom
.
The time complexity of this function is O(5^(n/2)), as there are five choices for each pair of digits, and the recursion goes down to n/2 levels. The space complexity is O(n), due to the recursive function call stack.
|
|