Day 41, 91 Decode Ways

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

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

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
------------------------------------------------
similar to steps problem, with some extra conditions
Solution #1 simple recursion

class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.length() == 0 || s[0] == '0') return 0;
        if (s.length() == 1) return 1;
        int fix = 0;
        if (s.length() == 2) {
            fix = 1;
        }
        if (s[0] == '1' || (s[0] == '2' && s[1] < '7')) {
            return numDecodings(s.substr(1)) + numDecodings(s.substr(2)) + fix;
        }
        return numDecodings(s.substr(1));
    }
};

Solution #2 DP

class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.length() == 0 || s[0] == '0') {
            return 0;
        }
        vector<int> ways(s.length() + 1, 1);
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '0') {
                ways[i] = 0;
            }else {
                ways[i] = ways[i+1];
            }
            if (i+1 < s.length() && (s[i] == '1' || (s[i] == '2' && s[i+1] < '7'))) {
                ways[i] += ways[i+2];
            }
        }
        return ways[0];
    }
};

In Java, recursion with memoization

class Solution {
    private Map<String, Integer> map = new HashMap<>();
    public int numDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') return 0;
        if (s.length() == 1) {
            return 1;
        }
        
        int i = 0;
        String s1 = s.substring(1);
        if (map.containsKey(s1)) {
            i = map.get(s1);
        }else {
            i = numDecodings(s.substring(1)); 
            map.put(s.substring(1), i);
        }
        
        if (s.charAt(0) == '1' || (s.charAt(0) == '2' && s.charAt(1) < '7')) {
            
            String s2 = s.substring(2);
            int j = 0;
            
            if (map.containsKey(s2)) {
                j = map.get(s2);
            }else {
                j = numDecodings(s2); 
                map.put(s2, j);
            }
            
            int rt = 0;
            if (s.length() == 2) rt = 1;
            return i + j + rt;
        }
        
        return i;
    }
}

COME_BACK
写一下O(1) 空间复杂度