LeetCode 91: Decode Ways Solution

Master LeetCode problem 91 (Decode Ways), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

91. Decode Ways

Medium

String Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate through the input string and build an array to keep track of the number of ways to decode the substring up to that point. We can consider two cases for each digit:

If the current digit can be decoded on its own (i.e., it is not '0'), then the number of ways to decode up to this point is the same as the number of ways to decode the previous digit.
If the current digit, along with the previous digit, forms a valid code (i.e., it is between '10' and '26'), then we can also consider the number of ways to decode up to two digits before the current digit.

By considering these two cases, we can build our dynamic programming array and return the value at the end which represents the number of ways to decode the entire string.

Time complexity: O(n), where n is the length of the input string.
Space complexity: O(n) for the dynamic programming array.

Solution Code

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') {
            return 0;
        }
        
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            int oneDigit = Integer.parseInt(s.substring(i-1, i));
            int twoDigits = Integer.parseInt(s.substring(i-2, i));
            
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i-1];
            }
            
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i-2];
            }
        }
        
        return dp[n];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 91 (Decode Ways)?

This page provides optimized solutions for LeetCode problem 91 (Decode Ways) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 91 (Decode Ways)?

The time complexity for LeetCode 91 (Decode Ways) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 91 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 91 in Java, C++, or Python.

Back to LeetCode Solutions