Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 91 with 13 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 91 # by problem number
lcpy gen -s decode_ways # by problem name
"1" -> 'A', "2" -> 'B', ..., "26" -> 'Z'. Given a string s containing only digits, return the number of ways to decode it. Return 0 if it cannot be decoded.
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Input: s = "06"
Output: 0
Explanation: leading zero makes it invalid.
class Solution:
# Time: O(n)
# Space: O(1)
def num_decodings(self, s: str) -> int:
if not s:
return 0
num_ways_two_steps_behind: int = 1
num_ways_one_step_behind: int = 0 if s[0] == "0" else 1
for index in range(1, len(s)):
current_char: str = s[index]
previous_char: str = s[index - 1]
current_num_ways: int = 0
if current_char != "0":
current_num_ways += num_ways_one_step_behind
two_digit_value: int = int(previous_char + current_char)
if previous_char != "0" and 10 <= two_digit_value <= 26:
current_num_ways += num_ways_two_steps_behind
num_ways_two_steps_behind, num_ways_one_step_behind = (
num_ways_one_step_behind,
current_num_ways,
)
return num_ways_one_step_behind
| Time | Space |
|---|---|
| O(n) | O(1) |