Memoization

Decode Ways

• brute force DFS solution: O(2^N) Time

• improved: memo = DFS + hashMap

  • fetch from memo map

  • check index == s.length()

  • check s.charAt(index) != '0'

  • check s.substring(index, index + 1)

  • check s.substring(index, index + 2)

• make sure it's not start with '0'

• 面试时候推荐dfs->memo的思路

• Time: O(N), Space: O(N)

• 除非面试官要求optimal space complexity-> dp with rolling array

class Solution {
    /*
    memo = dfs + hashmap
    
    1. fetch from memo map
    2. check index == s.length()
    3. check s.charAt(index) == '0'
    4. check s.substring(index, index + 1)
    5. check s.substring(index, index + 2)
    */
     
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        return dfs(s, 0, new HashMap<>());
    }
    
    private int dfs(String s, int index, Map<Integer, Integer> memo) {
        if (memo.containsKey(index)) {
            return memo.get(index);
        }
        if (index == s.length()) {
            return 1;
        }
        if (s.charAt(index) == '0') {
            memo.put(index, 0);
            return 0;
        }
        int res = 0;
        if (index + 1 <= s.length()) {
            res += dfs(s, index + 1, memo);
        }
        if (index + 2 <= s.length() && (s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index + 1) < '7')) {
            res += dfs(s, index + 2, memo);
        }
        memo.put(index, res);
        return res;
    }
}