Decode Ways
A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' ->200Question Mark, 'B' = 2, ..., 'Z' = 26. Given a non-empty string containing only digits, determine the number of ways to decode it.
Constraints:
- 1 <= s.length <= 100
- s contains only digits
Examples:
Input: 12
Output: 2
Explanation: It could be decoded as 'AB' (1 2) or 'L' (12)
Input: 226
Output: 3
Explanation: It could be decoded as 'BZ' (2 26), 'VF' (2 2 6), or 'BBF' (2 2 6)
Solutions
Dynamic Programming
This solution uses dynamic programming to calculate the number of ways to decode the string. It initializes a dp array where dp[i] represents the number of ways to decode the string up to index i. It then iterates through the string, updating dp[i] based on whether the current character can be decoded separately or together with the previous character.
def numDecodings(s):
dp = [0] * (len(s) + 1); dp[0] = 1; for i in range(1, len(s) + 1):
if s[i - 1] != '0':
dp[i] += dp[i - 1]; if i >= 2 and '10' <= s[i - 2:i] <= '26':
dp[i] += dp[i - 2]; return dp[-1]Follow-up:
How would you modify the solution to handle cases where the input string contains non-digit characters?
