Decode Ways

We convert digits to letters: '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'. Given a string s, finding the count of possible decodings.

Example: s = "12"

• "1, 2" -> "AB"
• "12" -> "L"
• Output: 2

We use DP. Let dp[i] be the number of ways to decode the prefix s[0...i-1].

Transitions:

1. One Digit: If s[i-1] is '1'-'9', we can add dp[i-1] ways.
2. Two Digits: If s[i-2...i-1] is "10"-"26", we can add dp[i-2] ways.

Base case: dp[0] = 1 (empty string has 1 way).

Observe how we look back 1 step (single digit) and 2 steps (two digits) to sum up the valid ways.

Click 'Randomize' to try different strings.