LeetCode Solutions
    Decode Ways: From Simple to Complex

    Decode Ways: From Simple to Complex

    91. Decode Ways

    You get a string of digits. How many ways can you decode it back to letters A-Z?

    Each position has two choices: take one digit or take two digits.

    1. If both one-digit and two-digit are valid, add the previous two counts
    2. If only one-digit is valid, carry forward the previous count
    3. If neither works, return 0

    The base case has just one way. When both choices work, you get a Fibonacci-like sequence.

    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;	// compressed dp[i-1]
    int w2=1;	// compressed 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;
}

// check single digit validity
bool valid(char c) {
    return c != '0';
}

// check double digit validity
bool valid(char c1, char c2) {
    int num=(c1-'0')*10+(c2-'0');
    return num>=10 && num<=26;
}

    639. Decode Ways II

    Now we add * wildcards that can represent any digit from 1-9. How many ways now?

    #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] = single digit ways + double digit ways
        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

    Counting Trailing Zeros in FactorialsDivisor Game Solution