Welcome back to the daily leetcode problems, day 25.

Link Problem

Solution:

• Using Dynamic Programming.

• Call f[i] is a result for string start at i.

• For each i, we will have two possible ways to make current values:

• 1. We can choose current i as a number.

     1. We can select i and i + 1 as a number if and only current values ≤ 2 and i + 1 values ≤ 6.

• We will see that many states are repeated, so we will use dynamic programming to avoid repetition.

Code:

class Solution {
public:

    int solve(vector<int>& f, string &s, int n) {
        if(n == s.size()) return 1;
        if(f[n] != -1) return f[n];
        int ways = 0;
        if(s[n] != '0')
            ways += solve(f, s, n + 1);
        if(n + 1 < s.size() && (s[n] == '1' || s[n] == '2' && s[n + 1] <= '6'))
            ways += solve(f, s, n + 2);
        return f[n] = ways;
    }

    int numDecodings(string s) {
        const int n = s.size();
        vector<int> f(n + 1, -1);
        return solve(f, s, 0);
    }
};