LeetCode 题解
    Decode Ways 系列

    Decode Ways 系列

     91. Decode Ways  给一串数字，求解码成 A-Z 有多少种解码方式？

    每一个位置都存在取一位和取两位的情况

    1. 如果取一位的时候为合法序列，两位也合法，种数就是前面两个之和
    2. 只有一位合法，种数顺延前一位的
    3. 都不合法，无法解码，返回种数为0

    初始解码方式都只有一种，如果两种取法都合法的话，那么种数就是一个斐波那契数列

    int numDecodings(string s) {
    if (s.empty() || s[0]=='0') return 0;
    if (s.size()==1) return 1;
    int n=s.size();
    int w1=1;	// 状态压缩为 dp[i-1]
    int w2=1;	// 状态压缩为 dp[i-2]

    for(int i=1;i<n;++i) {
        int p1=valid(s[i]);
        int p2=valid(s[i-1], s[i]);
        int w=0;
        if (!p1 && !p2) return 0;
        if (p1) w=w1;
        if (p2) w+=w2;
        w2=w1;
        w1=w;
    }
    return w1;
}

// 一位合法检查
bool valid(char c) {
    return c != '0';
}

// 两位合法检查
bool valid(char c1, char c2) {
    int num=(c1-'0')*10+(c2-'0');
    return num>=10 && num<=26;
}

     639. Decode Ways II 

    引入 * 号，可以表示 1-9 的数字，问解码方式？

    #define K 1000000007

int numDecodings(string s) {
    if (s.empty() || s[0]=='0') return 0;
    if (s.size()==1) {
        return s[0]=='*' ? 9 : 1;
    }
    int n=s.size();
    long dp[2]={1, count(s[0])};
    for(int i=1;i<n;++i) {
		// dp[i]=取一个种类数 + 取两个种类数
        long dpi=count(s[i])*dp[1]+count(s[i-1], s[i])*dp[0];
        dpi%=K;
        dp[0]=dp[1];
        dp[1]=dpi;
    }

    return dp[1];
}

int count(char c) {
    if(c=='0') return 0;
    if (c == '*') return 9;
    return 1;
}

int count(char c1, char c2) {
    if (c1=='*' && c2=='*') return 15;
    if (c1=='*') {
        return c2<='6' ? 2:1;
    } else if (c2=='*') {
        if (c1=='1') return 9;
        else if (c1=='2') return 6;
        else return 0;
    }

    int n = (c1-'0')*10+(c2-'0');
    return n>=10 && n<=26;
}

    #DP

    Construct Binary Tree 系列LRU cache