91. Decode Ways

So the easiest way, thought of course not the best one, it's to use a Depth first search to find out all the combinations.which works in this way.

actually we can just count the combinations. using DP. and because the encoded number of 'A'to'Z' is from '1' to '26' only has 1 or 2 digs. that means if we have an array, for exg. called DP, DP[i]records the ways of decoding from encodedString[0...i], we can see that DP[i] is depend on DP[i - 1], DP[i - 2]. and we can work from the top-down and which will only take O(n). both time and space. DP[0] = 1, because the first charater of the encoded message no double represents a letter (if we got a good encoded message which only has digits in it).

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if (n == 0 || s[0] == '0')return 0;

        int DP[n] = {0};

        if (s[0] >= '1' && s[0] <= '9')
            DP[0] = 1;
        if (n == 1)return DP[0];
        if (stoi(s.substr(0, 2)) <= 26)
            DP[1] = 2;
         else DP[1] = 1;
        if (s[1] =='0')DP[1]--;

        for (int i = 2; i < n; i++){
            if (s[i] != '0')DP[i] = DP[i - 1];
            if (stoi(s.substr(i - 1, 2)) <= 26 && s[i - 1] != '0')DP[i] += DP[i - 2];
        }

        return DP[n - 1];
    }
};

• test
  • think of '0's "0" "00" "100"
  • notice s.size()could be <=2

better answer maybe

• use three int instead of the array, as you only need DP[i - 1] and DP[i - 2], or maybe just two int

int numDecodings(string s) {
    if (!s.size() || s.front() == '0') return 0;
    // r2: decode ways of s[i-2] , r1: decode ways of s[i-1] 
    int r1 = 1, r2 = 1;

    for (int i = 1; i < s.size(); i++) {
        // zero voids ways of the last because zero cannot be used separately
        if (s[i] == '0') r1 = 0;

        // possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
        if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {
            r1 = r2 + r1;
            r2 = r1 - r2;
        }

        // one-digit letter, no new way added
        else {
            r2 = r1;
        }
    }

    return r1;
}

• create a function isvalid to help you see if it is valid

bool isValid(char a,char b){
    return a == '1'||(a == '2' && b <='6');
}
bool isValid(char a){
    return a != '0';
}

おまけ

s1 = s.substr(0, 1) ;

s = to_string(num);

a = stoi(s);

int DP[n] = {0};