Cinte's Leetcode Record
0%

91. Decode Ways

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

91. Decode Ways

dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int numDecodings(string s) {
        if(s.empty())
            return 0;
        vector<int> memo(s.size() + 1, 0);
        memo[0] = 1;
        memo[1] = s[0] != '0';
        for(int i = 1; i < s.size(); ++i)
        {
            if(memo[i] && s[i] != '0')
                memo[i + 1] += memo[i];
            if(memo[i - 1] && map.find(s.substr(i - 1, 2)) != map.end())
                memo[i + 1] += memo[i - 1];
        }
        return memo.back();
    }
private:
    unordered_set<string> map
    {
        "1",
        "2", 
        "3", 
        "4", 
        "5", 
        "6", 
        "7", 
        "8", 
        "9", 
        "10", 
        "11", 
        "12", 
        "13", 
        "14", 
        "15", 
        "16", 
        "17", 
        "18", 
        "19",
        "20", 
        "21", 
        "22", 
        "23",
        "24", 
        "25", 
        "26",
    };
};

每步检查当前的是否符合，如果符合，继承前一个的路数。

当前和前一个叠加的是否符合，如果符合，继承前前的路数

路数是相加的，因为这里分叉了

不用set
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numDecodings(string s) {
        if(s.empty())
            return 0;
        vector<int> memo(s.size() + 1, 0);
        memo[0] = 1;
        memo[1] = s[0] != '0';
        for(int i = 1; i < s.size(); ++i)
        {
            if(memo[i] && s[i] != '0')
                memo[i + 1] += memo[i];
            if(memo[i - 1] && stoi(s.substr(i - 1, 2)) <= 26 && stoi(s.substr(i - 1, 2)) >= 10)
                memo[i + 1] += memo[i - 1];
        }
        return memo.back();
    }    
};

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numDecodings(string s) {
        if(s.empty())
            return 0;
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = s[0] != '0';
        for(int i = 1; i < n; ++i)
        {
            if(s[i] != '0')
                dp[i + 1] += dp[i];
            int num = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if(10 <= num && num <= 26)
                dp[i + 1] += dp[i - 1];
        }
        return dp.back();
    }
};