# 91. 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 an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message`"12"`, it could be decoded as`"AB"`(1 2) or`"L"`(12).

The number of ways decoding`"12"`is 2.

Thoughts:

1. f[s]: number of way to decode string s
2. starting from the least significant digit to the most significant digit:
1. recursive function: f[s[i ... end]] =
1. decode as current char s[i] + rest substring: s[i+1...end] (s[i] == 0? 0: f[s[i + 1... end]])
2. decode as current char and next char s[i ... i+1] + rest substring: s[i+2...end] (if we can both decode s[i...i+1] and s[i+2...end])

Code Time: O(n), Space O(n^2)

``````class Solution {
public:
int numDecodings(string s) {
unordered_map <string, int> f;
unordered_map <string, int> m;
f.clear();
for(int i = 1; i <= 26; i++){
f[to_string(i)] = 1;
}
m = f; // m is the element dictionary

for(int i = s.length()-2; i>=0; i--){
string sec2end = s.substr(i + 1, s.length() - (i + 1));
string third2end = s.substr(i + 2, s.length() - (i + 2));

if(f.find(sec2end) != f.end() && s[i] != '0' ){

f[s.substr(i, s.length() - i)]+=f[s.substr(i + 1, s.length() - (i + 1))];
}

if(f.find(third2end)!=f.end() && m.find(s.substr(i,2))!=m.end()){

f[s.substr(i, s.length() - i)]+=f[third2end];
}

}

return f[s];
}
};
``````