解码方法

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
private:
    int calculate(const string& s, int start, vector<int>& dp) {
        if (start == s.length()) {
            return 1;
        }

        if (dp[start] != -1) {
            return dp[start];
        }

        int res;
        if (s[start] == '0') {
            res = 0;
        } else {
            res = calculate(s, start + 1, dp);
            if (start + 1 < s.length() && stoi(s.substr(start, 2)) <= 26) {
                res += calculate(s, start + 2, dp);
            }
        }

        dp[start] = res;

        return res;
    }
public:
    int numDecodings(string s) {
        vector<int> dp(s.length(), -1);
        return calculate(s, 0, dp);
    }
};