Last updated on March 1st, 2025 at 07:58 pm

Here, we see a Decode Ways LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming, String

Companies

Facebook, Microsoft, Uber

Level of Question

Medium

Decode Ways LeetCode Solution

1. 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 to "F" because of the leading zero ("6" is different from "06").

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Dynamic Programming (DP). Specifically, this problem is a variation of the Fibonacci Numbers pattern, where the solution to the current state depends on the solutions to the previous one or two states. This is because decoding a string can involve either a single character or a pair of characters, and the number of ways to decode depends on the valid combinations of these.

3. Code Implementation in Different Languages

3.1 Decode Ways C++

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        if (s.size() == 1) return 1;
        int len = s.size(), dp[len];
        dp[0] = 1;
        dp[1] = (s[0] == '1' || s[0] == '2' && s[1] < '7' ? 1 : 0) + (s[1] != '0');
        for (int i = 2; i < len; i++) {
            if (s[i] == '0' && (s[i - 1] > '2' || s[i - 1] == '0')) return 0;
            dp[i] = s[i] != '0' ? dp[i - 1] : 0;
            if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] < '7') dp[i] += dp[i - 2];
        }
        return dp[len - 1];  
    }
};

3.2 Decode Ways Java

class Solution {
    public int numDecodings(String s) {
	Integer[] memo = new Integer[s.length() + 1];
	return numDecodings(s, 0, memo);
}

private int numDecodings(String s, int index, Integer[] memo) {
	if (index == s.length()) {
		return 1;
	}
	if (s.charAt(index) == '0') {
		return 0;
	}
	if (memo[index] != null) {
		return memo[index];
	}
	int way1 = numDecodings(s, index + 1, memo);
	int way2 = 0;
	if (index < s.length() - 1 && Integer.parseInt(s.substring(index, index + 2)) <= 26) {
		way2 = numDecodings(s, index + 2, memo);
	}
	memo[index] = way1 + way2;
	return memo[index];
}
}

3.3 Decode Ways JavaScript

var numDecodings = function(s) {
  if (s == null || s.length === 0) return 0;
  if (s[0] === '0') return 0;

  const dp = new Array(s.length + 1).fill(0);

  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= s.length; i++) {
    const a = Number(s.slice(i - 1, i));  // last one digit
    if (a >= 1 && a <= 9) {
      dp[i] += dp[i - 1];
    }

    const b = Number(s.slice(i - 2, i));  // last two digits
    if (b >= 10 && b <= 26) {
      dp[i] += dp[i - 2];
    }
  }
  return dp[s.length];   
};

3.4 Decode Ways Python

class Solution(object):
    def numDecodings(self, s):
    	if not s:
		return 0

	dp = [0 for x in range(len(s) + 1)] 
	
	dp[0] = 1 
	dp[1] = 0 if s[0] == "0" else 1   #(1)

	for i in range(2, len(s) + 1): 
		# One step jump
		if 0 < int(s[i-1:i]) <= 9:    #(2)
			dp[i] += dp[i - 1]
		# Two step jump
		if 10 <= int(s[i-2:i]) <= 26: #(3)
			dp[i] += dp[i - 2]
	return dp[len(s)]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)

• The problem is a classic Dynamic Programming problem, where the solution to the current state depends on the solutions to previous states.
• The Fibonacci Numbers pattern is evident because the number of ways to decode up to index i depends on the sum of the ways to decode up to i-1 and i-2 (if valid).
• The space complexity can be optimized to O(1) by using two variables instead of a dp array, as only the last two states are needed at any point.