algoadvance

Leetcode 91. Decode Ways

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 that consists of digits, we need to return the total number of ways to decode it.

For example, given the message "12", it could be decoded as "AB" (1 2) or "L" (12). Therefore, the input "12" should return 2.

You are required to implement a function public int numDecodings(String s) to find the total number of ways to decode a string s.

Clarifying Questions

  1. Empty String Case:
    • Q: Should an empty string return 0 or 1 as output?
    • A: An empty string should return 0 because there are no ways to decode it.
  2. Invalid Characters:
    • Q: Can there be any invalid characters other than digits in the input?
    • A: No, the input will always consist of digits only, ranging from ‘0’ to ‘9’.
  3. Leading Zeros:
    • Q: How should we handle leading zeros or zeros in general, as they don’t correspond to any letter?
    • A: We should consider them invalid if they cannot form a valid two-digit number (like ‘10’, ‘20’) with the preceding number.

Strategy

To solve this problem, we can use dynamic programming. The key idea is to use a DP array where dp[i] represents the number of ways to decode the substring s[0...i-1].

Here are the steps:

  1. Initialization:
    • If s is empty, return 0.
    • Initialize a dp array of size n + 1 where n is the length of the input string s.
    • dp[0] = 1 because there’s one way to decode an empty string.
    • dp[1] = 1 if s[0] is not ‘0’ (if it is, return 0).
  2. DP Transition:
    • Traverse the string from the second character onwards.
    • For each character s[i], there are two scenarios:
      • Single digit decode: If s[i-1] is not ‘0’, set dp[i + 1] += dp[i].
      • Two-digit decode: If the substring s[i-2...i-1] forms a valid number between “10” to “26”, set dp[i + 1] += dp[i-1].
  3. **Return the result in dp[n], which represents the number of ways to decode the entire string s.

Code

public class DecodeWays {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1; // base case: empty string
        
        // If the first character is not '0', there is one way to decode it.
        // Otherwise, there's no way to decode it.
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        
        for (int i = 2; i <= n; i++) {
            int singleDigit = Integer.parseInt(s.substring(i - 1, i));
            int doubleDigit = Integer.parseInt(s.substring(i - 2, i));
            
            // Single digit decode
            if (singleDigit >= 1 && singleDigit <= 9) {
                dp[i] += dp[i - 1];
            }
            
            // Double digit decode
            if (doubleDigit >= 10 && doubleDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n];
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we only perform a constant amount of work for each character in the string.

Space Complexity

The space complexity is O(n) as well, due to the extra space required for the dp array of size n + 1.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI