Decode Ways
Problem Description
A message encoded as digits maps to letters: '1'→'A', '2'→'B', ..., '26'→'Z'. Given a string s of digits, return the number of ways to decode it.
Example 1:
Input: s = "12"
Output: 2 ("AB" or "L")
Example 2:
Input: s = "226"
Output: 3 ("BZ", "VF", "BBF")
Example 3:
Input: s = "06"
Output: 0 (leading zero, invalid)
DE Shaw Tier 3 — LC 91.
DP: dp[i] = number of ways to decode s[0..i-1].
If s[i-1] != '0': dp[i] += dp[i-1] (single digit decode)
If s[i-2..i-1] is 10..26: dp[i] += dp[i-2] (two digit decode)
Example Test Cases
Example 1
Input: ["12"]
Expected: 2
Example 2
Input: ["226"]
Expected: 3
Example 3
Input: ["06"]
Expected: 0
Example 4
Input: ["11106"]
Expected: 2
Run your code to see the results