91. Decode Ways LeetCode Solution

In this guide, you will get 91. Decode Ways LeetCode Solution with the best time and space complexity. The solution to Decode Ways problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Decode Ways solution in C++
Decode Ways solution in Java
Decode Ways solution in Python
Additional Resources

Problem Statement of Decode Ways

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:
“1” -> ‘A’
“2” -> ‘B’
…
“25” -> ‘Y’
“26” -> ‘Z’
However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (“2” and “5” vs “25”).
For example, “11106” can be decoded into:

“AAJF” with the grouping (1, 1, 10, 6)
“KJF” with the grouping (11, 10, 6)
The grouping (1, 11, 06) is invalid because “06” is not a valid code (only “6” is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.
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”). In this case, the string is not a valid encoding, so return 0.

Constraints:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

91. Decode Ways LeetCode Solution in C++

class Solution {
 public:
  int numDecodings(string s) {
    const int n = s.length();
    // dp[i] := the number of ways to decode s[i..n)
    vector<int> dp(n + 1);
    dp[n] = 1;  // ""
    dp[n - 1] = isValid(s[n - 1]);

    for (int i = n - 2; i >= 0; --i) {
      if (isValid(s[i]))
        dp[i] += dp[i + 1];
      if (isValid(s[i], s[i + 1]))
        dp[i] += dp[i + 2];
    }

    return dp[0];
  }

 private:
  bool isValid(char c) {
    return c != '0';
  }

  bool isValid(char c1, char c2) {
    return c1 == '1' || c1 == '2' && c2 < '7';
  }
};
/* code provided by PROGIEZ */

91. Decode Ways LeetCode Solution in Java

class Solution {
  public int numDecodings(String s) {
    final int n = s.length();
    // dp[i] := the number of ways to decode s[i..n)
    int[] dp = new int[n + 1];
    dp[n] = 1; // ""
    dp[n - 1] = isValid(s.charAt(n - 1)) ? 1 : 0;

    for (int i = n - 2; i >= 0; --i) {
      if (isValid(s.charAt(i)))
        dp[i] += dp[i + 1];
      if (isValid(s.charAt(i), s.charAt(i + 1)))
        dp[i] += dp[i + 2];
    }

    return dp[0];
  }

  private boolean isValid(char c) {
    return c != '0';
  }

  private boolean isValid(char c1, char c2) {
    return c1 == '1' || c1 == '2' && c2 < '7';
  }
}
// code provided by PROGIEZ

91. Decode Ways LeetCode Solution in Python

class Solution:
  def numDecodings(self, s: str) -> int:
    n = len(s)
    # dp[i] := the number of ways to decode s[i..n)
    dp = [0] * n + [1]

    def isValid(a: str, b=None) -> bool:
      if b:
        return a == '1' or a == '2' and b < '7'
      return a != '0'

    if isValid(s[-1]):
      dp[n - 1] = 1

    for i in reversed(range(n - 1)):
      if isValid(s[i]):
        dp[i] += dp[i + 1]
      if isValid(s[i], s[i + 1]):
        dp[i] += dp[i + 2]

    return dp[0]
 # code by PROGIEZ