A message of letters A to Z was encoded as numbers using "A" -> "1", "B" -> "2", ..., "Z" -> "26". Given the digit string s, return the number of ways to decode it back into letters. A group cannot start with 0, so "06" is not a valid code for F. Return 0 if no decoding exists.
- 1 <= s.length <= 100
- s contains only digits and may contain leading zeros
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force recursion splits off one or two digits at every position, roughly Fibonacci many calls. State: dp[i] = number of ways to decode the first i characters. Recurrence: the last letter is a single digit (valid when s[i-1] is 1 to 9, contributing dp[i-1]) or a two digit code (valid when s[i-2..i) is 10 to 26, contributing dp[i-2]). Base case: dp[0] = 1, the empty prefix has one (empty) decoding. Memoise the recursion or fill the table left to right; since each entry depends on the previous two only, two variables are enough.
Algorithm
- Set
prev2 = 1(dp[0]) andprev1 = 1 if s[0] != "0" else 0(dp[1]). - For
ifrom 2 ton, startcur = 0. - If
s[i-1]is not "0", addprev1. If the two digit numbers[i-2..i)is between 10 and 26, addprev2. - Shift
prev2 = prev1,prev1 = cur. - Return
prev1.
O(n)Space: O(1)* can stand for any digit 1 to 9.class Solution: def numDecodings(self, s: str) -> int: n = len(s) prev2 = 1 # dp[0]: empty prefix prev1 = 1 if s[0] != '0' else 0 # dp[1] for i in range(2, n + 1): cur = 0 if s[i - 1] != '0': cur += prev1 # single digit 1 to 9 two = int(s[i - 2:i]) if 10 <= two <= 26: cur += prev2 # two digits 10 to 26 prev2, prev1 = prev1, cur return prev1