August 04, 2019

91. Decode Ways

法1. Recursion (With Memorization)

Time = O(n^2), Space = O(n^2)
其中调用substring method的Time = O(n), Space = O(n)

class Solution {
    public int numDecodings(String s) {
        Map<String, Integer> visited = new HashMap<>();
        return numDecodings(s, visited);
    }
    
    private int numDecodings(String s, Map<String, Integer> visited) {
        if (visited.containsKey(s)) {
            return visited.get(s);
        }        
        if (s.length() == 0) { // find an answer, return 1
            return 1;
        }
        if (s.charAt(0) == '0') { // **begin** with 0, invalid, return 0 
            return 0;
        }
        if (s.length() == 1) { // string with a single character, return 1 (make sure s not go out of boundary)
            return 1;
        }
        int nums = 0;
        nums += numDecodings(s.substring(1), visited);
        if (Integer.parseInt(s.substring(0, 2)) <= 26) {
            nums += numDecodings(s.substring(2), visited);
        }
        visited.put(s, nums);
        return nums;
    }
}

优化：Use a pointer. 递归函数传index(pointer)而不是substring。 Time = O(n), Space = O(n)
现在index有多少种做法取决于前一个index有多少做法和前前index有多少做法(invalid filtered out).

class Solution {
    public int numDecodings(String s) {
        Map<Integer, Integer> visited = new HashMap<>();
        return numDecodings(s, 0, visited);
    }
    
    // i is the decode pointer
    private int numDecodings(String s, int i, Map<Integer, Integer> visited) {
        if (visited.containsKey(i)) {
            return visited.get(i);
        }  
        if (i == s.length()) { // find an answer, return 1
            return 1; 
        }
        if (s.charAt(i) == '0') { // begin with 0, invalid, return 0 
            return 0;
        }
        if (i == s.length() - 1) { // string with a single character, return 1 (make sure s not go out of boundary)
            return 1; 
        }
        int nums = 0;
        nums += numDecodings(s, i + 1, visited);
        if(Integer.parseInt(s.substring(i, i + 2)) <= 26) {
            nums += numDecodings(s, i + 2, visited);
        }
        visited.put(i, nums);
        return nums;
    }
}

法2. DP

Time = O(n), Space = O(n)

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // dp meaning: how many decode ways for s.substring(0,i)
        int[] numDecodings = new int[s.length() + 1];
        numDecodings[0] = 1;
        numDecodings[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i < numDecodings.length; i++) {
            int nums = 0;
            // substring that begins with 0 is invalid
            if (s.charAt(i - 1) != '0') { 
                nums += numDecodings[i - 1];
            }
            if (s.charAt(i - 2) != '0' && Integer.parseInt(s.substring(i - 2, i)) <= 26) {
                nums += numDecodings[i - 2];
            }  
            numDecodings[i] = nums;
        }
        return numDecodings[numDecodings.length - 1];
    }
}

优化空间 O(n) -> O(1):