91. Decode Ways.md

91. Decode Ways

思路

思路一

我们可以这样看待这个题。将s看成是一个充满障碍的路，每个数字代表一个障碍，我们需要从左到右通过这条路，需要满足的条件是:

• 一次只能越过一个或者两个障碍;
• 一次性越过的（一个或两个）障碍所代表的数属于[1,26]。

Path s: _ 2 _ 2 _ 6 _
Index:  0   1   2   3

对于上例，可能的路径就是0->1->2->3、0->2->3、0->1->3。

所以我么可以通过动态规划解此题，开辟一个大小为s.size()+1的数组dp, dp[i]代表从最左边(index=0)到达index=i的所有情况数，最终所求即dp的最后一个元素。所以dp[0]初始为1, 有两种方式可到达i:

1. 从i-1越过障碍s[i-1]到达i；
2. 从i-2越过障碍s[i-2]和s[i-1]到达i；

情况1需要满足的条件是s[i - 1] != 0，情况2需要满足的条件是s[i-2]和s[i-1]组成的数字属于[1,26]。

时空复杂度均为O(n)

思路二

仔细分析思路一发现，我们每次循环只需要用到dp[i]、dp[i - 1]和dp[i - 2]，所以我们没必要开辟一个dp数组，而用cur、pre和pre_pre分别代表dp[i]、dp[i - 1]和dp[i - 2]就可以了。

时间复杂度O(n)，空间复杂度O(1)

C++

思路一

class Solution {
public:
    int numDecodings(string s) {
        if(s[0] == '0') return 0;
        vector<int>dp(s.size() + 1, 0);
        dp[0] = 1;
        for(int i = 1; i < dp.size(); i++){
            dp[i] = (s[i - 1] == '0') ? 0: dp[i - 1]; // 方式1
            if(i > 1){ // 方式2
                if(s[i - 2] == '1') dp[i] += dp[i - 2];
                else if(s[i - 2] == '2' && s[i - 1] < '7') dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

思路二

class Solution {
public:
    int numDecodings(string s) {
        if(s[0] == '0') return 0;
        int cur, pre = 1, pre_pre;
        for(int i = 1; i < s.size() + 1; i++){
            cur = (s[i - 1] == '0') ? 0: pre;
            if(i > 1){
                if(s[i - 2] == '1') cur += pre_pre;
                else if(s[i - 2] == '2' && s[i - 1] < '7') cur += pre_pre;
            }
            pre_pre = pre;
            pre = cur;
        }
        return cur;
    }
};