## Algorithm

Problem Nmae: 91. Decode Ways

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, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"11106"` can be mapped into:

• `"AAJF"` with the grouping `(1 1 10 6)`
• `"KJF"` with the grouping `(11 10 6)`

Note that the grouping `(1 11 06)` is invalid because `"06"` cannot be mapped into `'F'` since `"6"` is different from `"06"`.

Given a string `s` containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

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

Example 2:

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

Example 3:

```Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
```

Constraints:

• `1 <= s.length <= 100`
• `s` contains only digits and may contain leading zero(s).

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int numDecodings(char* s) {
int a, b, c;
char p, t;

/* a b c
2267312
0 1
*/
a = 0;
b = 1;
c = 0;
p = 'x';    // anything other than '1' or '2'

while (t = *s ++) {
if (t == '0') {
if (p != '1' && p != '2') {
return 0;
}
c = a;
} else {
c = b;
if (p == '1' || (p == '2' && t  < = '6')) {
c += a;
}
}
a = b;
b = c;
p = t;
}

return c;
}
``````
Copy The Code &

Input

cmd
s = "12"

Output

cmd
2

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int numDecodings(string s) {
/** dp[i] =
* value                            Example
* 0                                00, 30, 80 - invalid ending
* dp[i-2]                          10, 20     - valid ending with 0
* dp[i-2]                          08, 09     - s[i - 1] == '0'
* dp[i-1] + dp[i-2]                11, 16     - valid ending
* dp[i-1]                          32, 56     - large ending, decrease i by 1
*/
if(s.size() == 0 || s[0] == '0') return 0;
vector<int>dp(s.size());
dp[0] = 1;
for(int i = 1; i < s.size(); i++){
if(s[i] == '0'>{
if(s[i - 1] == '0' || s[i - 1] - '0' > 2) return 0;
dp[i] = (i==1) ? dp[0] : dp[i - 2];
}
else if(s[i - 1] == '0') dp[i] = dp[i - 2];
else if(stoi(s.substr(i - 1, 2)) <= 26) dp[i] = (i==1) ? dp[0] + 1 : dp[i - 1] + dp[i - 2];
else dp[i] = dp[i - 1];
}
return dp[s.size(>-1];
}
};
``````
Copy The Code &

Input

cmd
s = "12"

Output

cmd
2

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {

public int numDecodings(String s) {
Map map = new HashMap<>();
return helper(s, 0, map);
}

private int helper(String s, int idx, Map < Integer, Integer> map) {
if (map.containsKey(idx)) {
return map.get(idx);
}
if (idx == s.length()) {
return 1;
}
if (s.charAt(idx) == '0') {
return 0;
}
if (idx == s.length() - 1) {
return 1;
}
int result = helper(s, idx + 1, map);
if (Integer.parseInt(s.substring(idx, idx + 2))  < = 26) {
result += helper(s, idx + 2, map);
}
map.put(idx, result);
return result;
}
}
``````
Copy The Code &

Input

cmd
s = "226"

Output

cmd
3

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numDecodings = function(s) {
if(s == null || s.length === 0) return 1
if(s[0] === '0') return 0
const set = new Set()
const n = s.length
for(let i = 1; i <= 26; i++) {
}
const dp = Array(n + 1).fill(0)
dp[0] = dp[1] = 1
for(let i = 2; i  < = n; i++) {
if(set.has(s[i - 2] + s[i - 1])) dp[i] += dp[i - 2]
if(set.has(s[i - 1])> dp[i] += dp[i - 1]
}
return dp[n]
};
``````
Copy The Code &

Input

cmd
s = "06"

Output

cmd
s = "06"

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numDecodings(self, s):
if s[0] == "0": return 0
dp1 = dp2 = 1
for i in range(1, len(s)):
if s[i] == "0" and (s[i - 1] == "0" or s[i - 1] >= "3"): return 0
dp1, dp2 = [dp2, dp1] if s[i] == "0" else [dp2, dp2 + dp1] if "10" <= s[i -1: i + 1] <= "26" else [dp2, dp2]
return dp2
``````
Copy The Code &

Input

cmd
s = "06"

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _091_DecodeWays
{
public int NumDecodings(string s)
{
if (s.Length == 0) return 0;

int[] memo = new int[s.Length + 1];
memo[s.Length] = 1;
memo[s.Length - 1] = s[s.Length - 1] == '0' ? 0 : 1;

for (var i = s.Length - 2; i >= 0; i--)
{
if (s[i] == '0') memo[i] = 0;
else
memo[i] = int.Parse(s.Substring(i, 2))  < = 26 ? memo[i + 1] + memo[i + 2] : memo[i + 1];
}
return memo[0];
}
}
}
``````
Copy The Code &

Input

cmd
s = "12"

Output

cmd
2