Log inSign up
mediumLeetCodeNot Started

Decode Ways

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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). For example, "11106" can be mapped into: - "AAJF" with the grouping (1 1 10 6) - "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.

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 because leading zeroes are invalid.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model multi-character decoding as jump transitions in DP.
  • Thoroughly validate boundary and zero edge cases.
  • Reduce O(n) array storage to O(1) rolling state variables.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Decoding string of numeric characters into alphabet letters.
  • Each letter consumes either 1 or 2 characters.
  • Invalid zero digits constrain transitions.

Algorithmic Decision Tree:

  • 1-character jump -> valid if char in 1..9.
  • 2-character jump -> valid if substring in 10..26.

Connected Patterns:

Climbing StairsWord BreakRestore IP Addresses

1. Recursive Branching

Intuition

At each index i, branch into decoding a 1-digit number and/or a 2-digit number.

Algorithm

  1. Define dfs(i).
  2. If i == s.length, return 1.
  3. If s[i] == '0', return 0.
  4. Option 1: decode 1 digit -> ways = dfs(i + 1).
  5. Option 2: if i + 1 < s.length and substring s[i..i+1] is between 10 and 26, ways += dfs(i + 2).
  6. Return ways.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4using namespace std;
5
6int dfs(int i, const string& s) {
7 if (i == (int)s.length()) return 1;
8 if (s[i] == '0') return 0;
9
10 int ways = dfs(i + 1, s);
11 if (i + 1 < (int)s.length()) {
12 int twoDigit = (s[i] - '0') * 10 + (s[i + 1] - '0');
13 if (twoDigit >= 10 && twoDigit <= 26) {
14 ways += dfs(i + 2, s);
15 }
16 }
17 return ways;
18}
19
20int numDecodingsRec(string s) {
21 return dfs(0, s);
22}
23
24int main() {
25 string s = "226";
26 cout << "Decode Ways (Recursive): " << numDecodingsRec(s) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Dynamic Programming Tabulation

Intuition

Build an array dp of size n + 1 where dp[i] is the number of ways to decode prefix s[0..i-1].

Algorithm

  1. If s[0] == '0', return 0.
  2. Create array dp of size n + 1 filled with 0.
  3. dp[0] = 1, dp[1] = 1.
  4. For i = 2 to n:
  5. If s[i - 1] != '0': dp[i] += dp[i - 1]
  6. twoDigit = int(s[i-2..i-1])
  7. If 10 <= twoDigit <= 26: dp[i] += dp[i - 2]
  8. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7int numDecodingsTab(string s) {
8 if (s.empty() || s[0] == '0') return 0;
9 int n = s.length();
10 vector<int> dp(n + 1, 0);
11 dp[0] = 1;
12 dp[1] = 1;
13
14 for (int i = 2; i <= n; i++) {
15 if (s[i - 1] != '0') {
16 dp[i] += dp[i - 1];
17 }
18 int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
19 if (twoDigit >= 10 && twoDigit <= 26) {
20 dp[i] += dp[i - 2];
21 }
22 }
23 return dp[n];
24}
25
26int main() {
27 string s = "226";
28 cout << "Decode Ways (Tabulation): " << numDecodingsTab(s) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) for dp table

3. O(1) Space Rolling Variables

Intuition

Maintain two variables prev2 and prev1 tracking dp[i-2] and dp[i-1].

Algorithm

  1. If s[0] == '0', return 0.
  2. prev2 = 1, prev1 = 1.
  3. For i = 1 to s.length - 1:
  4. curr = 0
  5. If s[i] != '0': curr += prev1
  6. twoDigit = int(s[i-1..i])
  7. If 10 <= twoDigit <= 26: curr += prev2
  8. prev2 = prev1, prev1 = curr.
  9. Return prev1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4using namespace std;
5
6int numDecodingsOptimal(string s) {
7 if (s.empty() || s[0] == '0') return 0;
8 int prev2 = 1;
9 int prev1 = 1;
10
11 for (size_t i = 1; i < s.length(); i++) {
12 int curr = 0;
13 if (s[i] != '0') {
14 curr += prev1;
15 }
16 int twoDigit = (s[i - 1] - '0') * 10 + (s[i] - '0');
17 if (twoDigit >= 10 && twoDigit <= 26) {
18 curr += prev2;
19 }
20 prev2 = prev1;
21 prev1 = curr;
22 }
23 return prev1;
24}
25
26int main() {
27 string s = "226";
28 cout << "Decode Ways (Optimal O(1) Space): " << numDecodingsOptimal(s) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive BranchingO(2^n)O(n)Exhaustive branching over 1-digit and 2-digit decodings.Redundant prefix calls
2.DP TabulationO(n)O(n)dp array tracking prefix decoding counts.Table allocation
3.Rolling VariablesOptimalO(n)O(1)Track prev2 and prev1 scalars.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating 0 as valid 1-digit decode (letters map from 1 to 26, not 0 to 25).

Pitfall 2:

Allowing two-digit values outside [10, 26] (e.g. 06 or 27).

Crucial Edge Cases to Validate:

  • s starts with 0: Output is 0 immediately.
  • Contains 00 or 30, 40...: Output is 0 (unencodable zeros).
  • Single character: 0 -> 0; 1-9 -> 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explicitly test the edge cases 0, 10, 27, and 100 during your code walkthrough to demonstrate mastery of zero-handling.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the string 10 have only 1 way to decode, while 100 has 0 ways to decode?

Back to DSA Sheet