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

---
## 我的作法
我使用的是遞迴的做法，對於字串裡面有'0'的要特別去做很多if的判斷。
遞迴主要想法:
* numDecodings(s) = numDecodings(s+1) + numDecodings(s+2)。
其中s為reference。
* 初始條件為:
* 遞迴到字串剩下2個字元以下
* 對於'0'字元的各種判斷

## C code

int numDecodings(char * s)
{
    if(s[1] == '\0')//遞迴剩下一個字元
    {
        if(s[0] == '0')return 0;
        else return 1;   
    }
    if(s[2] == '\0')//遞迴剩下兩個字元
    {
        if(s[0] == '0') return 0;
        if(s[1] == '0')
        {
            if(s[0]-48 > 2) return 0;
            else return 1;   
        }
        if(((int)(s[0]-48) * 10 + (int)(s[1]-48)) > 26) return 1;
        else return 2;
    }
    //以下是遞迴剩下三個字元
    if(s[0] == '0') return 0;
    if(s[1] == '0')
    {
        if(s[0]-48 > 2) return 0;
        else return numDecodings(s+2);
    }
    if(((int)(s[0]-48) * 10 + (int)(s[1]-48)) > 26)
        return numDecodings(s+1);
    else
    {
        return numDecodings(s+1) + numDecodings(s+2);
    }
}

## 成績