How do you approach Decode Ways?

Use dynamic programming - dp[i] represents the number of ways to decode the first i characters.

What is the time complexity of Decode Ways?

Time complexity: O(n). Space complexity: O(1) with space optimization.

What are common mistakes on Decode Ways?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Decode Ways

MediumAlgorithms

Description

A message containing letters from `A-Z` can be encoded into numbers using the following 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 above (there may be multiple ways). 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.

Example 1

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2

Input: s = "226"

Output: 3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero.

Constraints

- 1 <= s.length <= 100 - s contains only digits and may contain leading zeros.

Decode Ways: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 8 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Use dynamic programming - dp[i] represents the number of ways to decode the first i characters.
A single digit can be decoded if it's 1-9 (not 0).
Two digits can be decoded if they form a number between 10 and 26.

The optimal approach

Show the approach: Dynamic Programming

dp[i] = number of ways to decode the substring s[0..i-1]. For each position, check if the single digit is valid (1-9) and if the two-digit number is valid (10-26).

Time: O(n)
Space: O(1) with space optimization

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.