Decode Ways

Medium

One digit or two, if valid

Problem

Count the ways to decode a digit string where 1->A ... 26->Z.

In simple words

Ways to decode up to a spot = ways using one digit + ways using a valid two-digit (10-26) pair.

The idea

The count of decodings ending at position i is the count from i-1 when the single digit is 1..9, plus the count from i-2 when the two-digit number is 10..26. Zero is the awkward case: it decodes nothing on its own.

The trick

A '0' must pair with a preceding 1 or 2, or the string is undecodable.
Two rolling variables give O(1) space.
Leading zero means zero ways.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

226

1/2

Optimal

timeO(n)spaceO(1)

1dp[i]=dp[i-1](if s[i]!='0') + dp[i-2](if s[i-1..i] in 10..26)

Input

array: [226]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: s = "12"
Output:: 2
Explanation:: "AB" (1,2) or "L" (12) → 2 ways.

Example 2

Input:: s = "226"
Output:: 3
Explanation:: 2-2-6, 22-6, 2-26 → 3 ways.

Example 3

Input:: s = "06"
Output:: 0
Explanation:: Leading 0 can't decode → 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.