-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathnum_decodings.py
More file actions
74 lines (60 loc) · 1.85 KB
/
num_decodings.py
File metadata and controls
74 lines (60 loc) · 1.85 KB
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
"""
Decode Ways
Given an encoded message of digits, count the total number of ways to
decode it where 'A' = 1, 'B' = 2, ..., 'Z' = 26.
Reference: https://leetcode.com/problems/decode-ways/
Complexity:
Time: O(n)
Space: O(1) for num_decodings, O(n) for num_decodings2
"""
from __future__ import annotations
def num_decodings(enc_mes: str) -> int:
"""Count decoding ways using constant-space iteration.
Args:
enc_mes: String of digits representing the encoded message.
Returns:
Total number of ways to decode the message.
Examples:
>>> num_decodings("12")
2
>>> num_decodings("226")
3
"""
if not enc_mes or enc_mes[0] == "0":
return 0
last_char, last_two_chars = 1, 1
for i in range(1, len(enc_mes)):
last = last_char if enc_mes[i] != "0" else 0
last_two = (
last_two_chars
if int(enc_mes[i - 1 : i + 1]) < 27 and enc_mes[i - 1] != "0"
else 0
)
last_two_chars = last_char
last_char = last + last_two
return last_char
def num_decodings2(enc_mes: str) -> int:
"""Count decoding ways using a stack-based approach.
Args:
enc_mes: String of digits representing the encoded message.
Returns:
Total number of ways to decode the message.
Examples:
>>> num_decodings2("12")
2
>>> num_decodings2("226")
3
"""
if not enc_mes or enc_mes.startswith("0"):
return 0
stack = [1, 1]
for i in range(1, len(enc_mes)):
if enc_mes[i] == "0":
if enc_mes[i - 1] == "0" or enc_mes[i - 1] > "2":
return 0
stack.append(stack[-2])
elif 9 < int(enc_mes[i - 1 : i + 1]) < 27:
stack.append(stack[-2] + stack[-1])
else:
stack.append(stack[-1])
return stack[-1]