DSA problem

Decode Ways

MediumString DPPattern: String DPtop150MetaAmazonMicrosoftAppleBloomberg

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 the mapping (there may be multiple ways). For example, "11106" can be mapped into "AAJF" (1 1 10 6) or "KJF" (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. The test cases are generated so that the answer fits in a 32-bit integer. If a decoding is impossible (for example a string starting with '0' or containing "30"), return 0.

This is fundamentally a one-dimensional string DP. At each position i, the number of decodings of s[0..i) depends on whether the last one or two characters form a valid letter encoding. The recurrence resembles a constrained Fibonacci: take the last single digit if it is non-zero, plus the last two digits if they form a value in [10, 26].

The optimal approach defines dp[i] as the number of ways to decode the prefix s[0..i). Base case dp[0] = 1 (the empty string has one decoding). The transitions are: add dp[i-1] if s[i-1] != '0', and add dp[i-2] if the two-digit number s[i-2..i) is in [10, 26]. This runs in O(n) time and can be reduced from O(n) to O(1) space by tracking only the last two values.

Examples

Constraints

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

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

stringdynamic-programming

Browse all DSA problems