[Problem]

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.

[Analysis]
方法一：递归
    最开始蛋疼的用了这个方法，f(s, begin, end) = f(s, begin+1, end) + f(s, begin+2, end)，表示对s进行解码的时候，可以将s[begin]单独解码，也可以将s[begin,begin+1]作为一个整体解码，当然需要对s[begin]和s[begin, begin+1]进行check，确保这样是合法的。
    用这个方法过Small Judge没问题，但是过Large Judge肯定就TLE了。

方法二：动态规划
    从后往前扫描，用dp[i]表示对s[i:n]解码的方法数，那么，
（1）如果s[i]单独解码，则dp[i] += dp[i+1]，前提要求s[i+1:n]可以解码成功，即dp[i+1] > 0
（2）如果s[i, i+1]联合解码，则dp[i] += dp[i+2]，前提要求s[i+2:n]可以解码成功，即dp[i+2] > 0
注意判断边界条件。总的复杂度为O(n)


[Solution]
方法一：递归(过Small Judge没问题，过Large Judge会TLE)

class Solution {
public:
    // convert digital string into letter string
    bool check(string s){
        int len = s.length();
   
        // invalid
        if(len <= 0 || len > 2){
            return false;
        }
        else if(len == 1){
            if(s[0] <= '0' || s[0] > '9'){
                return false;
            }
            else{
                return true;
            }
        }
        else{
            if((s[0] <= '0' || s[0] > '2') || (s[1] < '0' || s[1] > '9') || (s[0] == '2' && s[1] > '6')){
                return false;
            }
            else{
                return true;
            }
        }
    }
   
    // decode
    int decode(string s, int begin, int end){
        int res = 0;
       
        // valid
        if(begin <= end && end < s.length()){
            // decode in one way
            if(begin == end){
                if(check(s.substr(begin, 1)) == true){
                    res = 1;
                }
            }
            // decode in two ways
            else{
                // decode with one letter
                bool valid = check(s.substr(begin, 1));
                if(valid){
                    res += decode(s, begin+1, end);
                }
   
                // decode with two letters
                valid = check(s.substr(begin, 2));
                if(valid){
                    // can be decoded in more ways
                    if(begin + 2 <= end){
                        res += decode(s, begin+2, end);
                    }
                    // can be decoded in one way
                    else{
                        res += 1;
                    }
                }
            }
        }
        return res;
    }
   
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return decode(s, 0, s.length()-1);
    }
};

方法二：动态规划

class Solution {
public:
    // convert digital string into letter string
    bool check(string s){
        int len = s.length();
   
        // invalid
        if(len <= 0 || len > 2){
            return false;
        }
        else if(len == 1){
            if(s[0] <= '0' || s[0] > '9'){
                return false;
            }
            else{
                return true;
            }
        }
        else{
            if((s[0] <= '0' || s[0] > '2') || (s[1] < '0' || s[1] > '9') || (s[0] == '2' && s[1] > '6')){
                return false;
            }
            else{
                return true;
            }
        }
    }
   
    // decoding
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len = s.length();
        if(len <= 0)return 0;
   
        // not empty
        int dp[len];
        memset(dp, 0, sizeof(dp));
   
        // dynamic search
        for(int i = len - 1; i >= 0; --i){
            // s[i] decode with itself
            if(check(s.substr(i, 1))){
                // the last letter
                if(i + 1 >= len){
                    dp[i] += 1;
                }
                else{
                    // s[i+1:n] can be decoded
                    if(dp[i + 1] > 0){
                        dp[i] += dp[i + 1];
                    }
                }
            }
   
            // s[i] can be decode with s[i+1]
            if(i <= len - 2 && check(s.substr(i, 2))){
                if(i + 2 >= len){
                    dp[i] += 1;
                }
                else{
                    // s[i+2:n] can be decode
                    if(dp[i + 2] > 0){
                        dp[i] += dp[i + 2];
                    }
                }
            }
        }
        return dp[0];
    }
};

说明：版权所有，转载请注明出处。 Coder007的博客