The basic idea is we can compose all possible numbers in the string format ["1","2",....,"26"] so the question came to a DP question with

f(n) = f(n-1) (if char[n-1] is valid 1-9) + f(n-2) (if substring [n-2,n] is in the set.

```
class Solution {
public int numDecodings(String s) {
Set<String> vals = new HashSet<String>();
for (int i = 1; i <= 26; i++) {
vals.add(i + "");
}
int[] dp = new int[s.length() + 1];
dp[0] = s.length() == 0 ? 0 : 1;
for (int i = 1; i <= s.length(); i++) {
if (i > 1 && vals.contains(s.substring(i-2, i))) {
dp[i] += dp[i-2];
}
if (s.charAt(i-1) >= '1' && s.charAt(i-1) <= '9') {
dp[i] += dp[i-1];
}
}
return dp[s.length()];
}
}
```