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

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

Follow up