## Description

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).
``````

## Solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 `````` ``````func numDecodings(s string) int { if len(s) == 0 || s == '0' { return 0 } dp := make([]int, len(s)+1) dp = 1 dp = 1 for i := 1; i < len(s); i++ { if s[i] == '0' { if s[i-1] == '1' || s[i-1] == '2' { // if this number is '0' // the previous number must be '1' or '2' // and the previous solution(dp[i]) should return to dp[i-1] // dp[i] = dp[i-1] dp[i+1] = dp[i-1] } else { return 0 } } else if s[i-1] == '1' || (s[i-1] == '2' && s[i]-'0' <= 6) { // if this number is not '0' // like 226, when i is 2, number is 6 // it can be splitted as "2|26" or "22|6" // so it can be from  and  dp[i+1] = dp[i] + dp[i-1] } else { // else there is only one way dp[i+1] = dp[i] } } return dp[len(s)] }``````