FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithms/algorithms/math/generate_strobogrammtic.py at main · keon/algorithms · GitHub
keon
/
algorithms
Public
Notifications
You must be signed in to change notification settings
Fork
4.7k
Star
25.5k
Code
Issues
2
Pull requests
3
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithms
/
algorithms
/
math
/
generate_strobogrammtic.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
111 lines (89 loc) · 2.75 KB
Breadcrumbs
algorithms
/
algorithms
/
math
/
generate_strobogrammtic.py
Copy path
File metadata and controls
111 lines (89 loc) · 2.75 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
"""
Generate Strobogrammatic Numbers
A strobogrammatic number looks the same when rotated 180 degrees. Generate
all strobogrammatic numbers of a given length or count them within a range.
Reference: https://en.wikipedia.org/wiki/Strobogrammatic_number
Complexity:
Time: O(5^(n/2)) for generation
Space: O(5^(n/2))
"""
from
__future__
import
annotations
def
gen_strobogrammatic
(
n
:
int
)
->
list
[
str
]:
"""Generate all strobogrammatic numbers of length n.
Args:
n: The desired length of strobogrammatic numbers.
Returns:
List of strobogrammatic number strings.
Examples:
>>> gen_strobogrammatic(2)
['88', '11', '96', '69']
"""
return
_helper
(
n
,
n
)
def
_helper
(
n
:
int
,
length
:
int
)
->
list
[
str
]:
"""Recursively build strobogrammatic numbers of length n.
Args:
n: Remaining length to fill.
length: Original target length.
Returns:
List of strobogrammatic number strings.
"""
if
n
==
0
:
return
[
""
]
if
n
==
1
:
return
[
"1"
,
"0"
,
"8"
]
middles
=
_helper
(
n
-
2
,
length
)
result
=
[]
for
middle
in
middles
:
if
n
!=
length
:
result
.
append
(
"0"
+
middle
+
"0"
)
result
.
append
(
"8"
+
middle
+
"8"
)
result
.
append
(
"1"
+
middle
+
"1"
)
result
.
append
(
"9"
+
middle
+
"6"
)
result
.
append
(
"6"
+
middle
+
"9"
)
return
result
def
strobogrammatic_in_range
(
low
:
str
,
high
:
str
)
->
int
:
"""Count strobogrammatic numbers within the given range [low, high].
Args:
low: Lower bound as a string.
high: Upper bound as a string.
Returns:
Count of strobogrammatic numbers in the range.
Examples:
>>> strobogrammatic_in_range("10", "100")
4
"""
res
:
list
[
str
]
=
[]
count
=
0
low_len
=
len
(
low
)
high_len
=
len
(
high
)
for
i
in
range
(
low_len
,
high_len
+
1
):
res
.
extend
(
_helper2
(
i
,
i
))
for
perm
in
res
:
if
len
(
perm
)
==
low_len
and
int
(
perm
)
<
int
(
low
):
continue
if
len
(
perm
)
==
high_len
and
int
(
perm
)
>
int
(
high
):
continue
count
+=
1
return
count
def
_helper2
(
n
:
int
,
length
:
int
)
->
list
[
str
]:
"""Recursively build strobogrammatic numbers including leading zeros.
Args:
n: Remaining length to fill.
length: Original target length.
Returns:
List of strobogrammatic number strings.
"""
if
n
==
0
:
return
[
""
]
if
n
==
1
:
return
[
"0"
,
"8"
,
"1"
]
mids
=
_helper
(
n
-
2
,
length
)
res
=
[]
for
mid
in
mids
:
if
n
!=
length
:
res
.
append
(
"0"
+
mid
+
"0"
)
res
.
append
(
"1"
+
mid
+
"1"
)
res
.
append
(
"6"
+
mid
+
"9"
)
res
.
append
(
"9"
+
mid
+
"6"
)
res
.
append
(
"8"
+
mid
+
"8"
)
return
res
Back
|
FazBrowse Home
|
New Git URL