Decode Ways medium

Problem Statement

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Steps and Explanation

The problem can be solved using dynamic programming. We create a dp array where dp[i] represents the number of ways to decode the string up to index i.

1. Base Cases:

   • dp[0] = 1 (empty string has one way to decode - itself)
   • dp[1] = 1 if the first digit is not '0', otherwise 0.

2. Iteration:

   • We iterate through the string from index 2.
   • For each index i, we consider two possibilities:
     • Decode the current digit alone: If s[i-1] is not '0', then we add dp[i-1] to dp[i].
     • Decode the last two digits together: If s[i-2]s[i-1] is within the range [10, 26], then we add dp[i-2] to dp[i].

3. Result:

   • dp[n] (where n is the length of the string) will contain the total number of ways to decode the entire string.

Code

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0; //Handle empty string case

        int[] dp = new int[n + 1];
        dp[0] = 1; // Base case: empty string has one decoding

        if (s.charAt(0) == '0') {
            dp[1] = 0; //if first char is 0, no ways to decode
        } else {
            dp[1] = 1; //Base case: single digit has one way
        }


        for (int i = 2; i <= n; i++) {
            int oneDigit = Integer.parseInt(s.substring(i - 1, i));
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));

            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i - 1];
            }
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n), due to the dp array. We can optimize this to O(1) by using only three variables to store the necessary dp values instead of the entire array. This optimization is left as an exercise for the reader but is a common space optimization technique for dynamic programming problems.