91. Decode Ways

• Difficulty: Medium

• Topics: String, Dynamic Programming

• Similar Questions:

  • Decode Ways II

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Solutions:

class Solution {
public:
    int numDecodings(string s) {

        int len = s.length();
        vector<int> cache(len, -1);

        return helper(s, 0, cache);
    }

    int helper(string s, int pos, vector<int>& cache) {
        if (pos > s.length())  return 0;
        if (pos == s.length())  return 1;
        if (cache[pos] != -1)   return cache[pos];

        int count = 0;

        if (s[pos] == '0')  return 0;
        count += helper(s, pos + 1, cache);
        if (pos + 1 < s.length()) {
            if (10*(s[pos] - '0') + s[pos + 1] - '0' <= 26) {
                count += helper(s, pos + 2, cache);
            }
        }

        cache[pos] = count;
        return count;
    }
};