> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/decode-ways.md).

# 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](https://www.geeksforgeeks.org/count-possible-decodings-given-digit-sequence/)
* [Leetcode](https://leetcode.com/problems/decode-ways/)
* [ProgramCreek](https://www.programcreek.com/2014/06/leetcode-decode-ways-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** "12"

**Output:** 2

**Explanation:** It could be decoded as "AB" (1 2) or "L" (12).
{% endtab %}

{% tab title="Example 2" %}
**Input:** "226"

**Output:** 3

**Explanation:** It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * 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];
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * 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];
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*