# 91. Decode Ways (Medium)

https://leetcode.com/problems/decode-ways/

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: "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

``````class Solution {

// For such kind of problems, you always need a map to keep track of visited situations so that you can
// speed up the execution efficiency.
Map<String, Integer> countMap = new HashMap<>();

public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 1;
}

if (countMap.containsKey(s)) {
return countMap.get(s);
}

// if s starts with '0', there is no substitute letters for "0" or "0?"
if (s.charAt(0) == '0') {
countMap.put(s, 0);

return 0;
}

// There is always substitute for single digit except "0"
int ans1 = numDecodings(s.substring(1));

int ans2 = 0;

// There is always substitute for 2 digit numbers in range [11, 26]
if (s.length() >= 2 && Integer.valueOf(s.substring(0, 2)) <= 26) {
ans2 = numDecodings(s.substring(2));
}

int ans = ans1 + ans2;

countMap.put(s, ans);

return ans;
}
}
``````