Decode Ways

The key idea

Count decodings position by position. The number of ways to decode the first i characters depends only on whether the last 1 digit forms a valid letter and whether the last 2 digits form a valid letter (10 to 26), so dp[i] = dp[i-1] (if single valid) + dp[i-2] (if pair valid).

Problem

A message containing letters from A-Z can be encoded into numbers using the mapping 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26".

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of this mapping (there may be many ways). For example, "11106" can be mapped into "AAJF" with the grouping (1 1 10 6) or "KJF" with the grouping (11 10 6). Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0. The test cases are generated so that the answer fits in a 32-bit integer.

Constraints

1 <= s.length <= 100
s contains only digits and may contain leading zero(s).

Examples

Input: s = "12" Output: 2

Input: s = "226" Output: 3

Input: s = "06" Output: 0

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →