91. Decode Ways ----M

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

Input: s = "12"

Output: 2

Explanation:

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"

Output: 3

Explanation:

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"

Output: 0

Explanation:

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

 

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

A:
 -------------------------------DP --------------using an 1D array--------------

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        vector<int> count(n + 1, 0);
        count[0] = 1; // so as to avoid checking boundary
        for (int i = 0; i < n; ++i) {
            if (s[i] >= '1' && s[i] <= '9')
                count[i + 1] = count[i];
            if (i > 0) {
                auto s2 = s.substr(i - 1, 2); // substr(startIndex, length)
                int val = stoi(s2);
                if (val >= 10 && val <= 26) {
                    count[i + 1] += count[i - 1];
                }
            }
        }
        return count[n];
    }
};

-------第二遍， ------ do not use array, just two previous value -----

class Solution {

public:

int numDecodings(string s) {

int pre = 1, prepre = 1;

for (int i = 0; i < s.length(); i++) {

// if stand alone

int cur = 0; // way of devode after adding this node;

if (s[i]>='1' && s[i] <= '9') {

cur += pre;

}

// if used former char

if (i > 0) {

auto tmp = stoi(s.substr(i - 1, 2));

if (tmp >= 10 && tmp <= 26) { // cannot accept 01 in this case

cur += prepre;

}

}

prepre = pre;

pre = cur;

}

return pre;

}

};

Mistakes：
1：  哎，一开始，竟然看成是输入为ABC类了。Tiger，你得多SB啊~~~
光为了简洁代码了，输入都没有检测，哎~~~~~~~

2： 当i-2<0的时候， 应该还是 +=  而不是简单的 =1
教训啊， 不要为了狗屁不如的代码简洁。 那个不重要，  首先要保证正确。

3： valid (2个char ）的时候， 首先要看，第一个是否是0, 如果是， 就不对。

Error：
1：开始没有考虑检查输入是否valid的情况， 例如输入为”0“
2：第一稿的时候，直很一厢情愿地，认为不会有"10"的输入， 或者说，不会有0这个数字。 艹，太SB 了。