91. Decode Ways

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "12"

Output: 2

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

Example 2

Input: "226"

Output: 3

Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Solutions

Solution 1

/**
 * Time complexity : O(N), where N is length of the string. We iterate the 
 *    length of dp array which is N+1.
 * Space complexity : O(N). The length of the DP array.
 */

class Solution {
    public int numDecodings(String s) {
        if(s.charAt(0) == '0') return 0;
        
        int n = s.length();
        int[] dp = new int[n+1];
        
        dp[0] = 1;
        dp[1] = (s.charAt(0) == '0')? 0: 1;
        
        for(int i = 2; i < n+1; i++) {
            if(s.charAt(i-1) != '0') 
                dp[i] += dp[i-1];
            
            int twoDigit = Integer.valueOf(s.substring(i-2, i));
            if(twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i-2];
            }
            
        }
        return dp[n];
    }
}

Solution 2

/**
 * Time complexity : O(N), where N is length of the string. We iterate the 
 *    length of dp array which is N+1.
 * Space complexity : O(1).
 */

class Solution {
    public int numDecodings(String s) {
        if(s == null || s.charAt(0) == '0') return 0;

        int[] dp = new int[2];
        dp[0] = 1;
        dp[1] = (s.charAt(0) == '0')? 0: 1;
        
        for(int i = 2; i < s.length()+1; i++) {
            char curr = s.charAt(i-1);
            char prev = s.charAt(i-2);
            int noOfWays = 0;
            // Check if successful single digit decode is possible.
            if(curr != '0') {
                noOfWays += dp[1];
            }
            // Check if successful two digit decode is possible.
            if(prev == '1' || (prev == '2' && curr <= '6')) {
                noOfWays += dp[0];
            }
            
            dp[0] = dp[1];
            dp[1] = noOfWays;
        }
        return dp[1];
    }
}

Follow up