public static int numDecodings(String s) {

    if (map.containsKey(s)) {
      return map.get(s);
    }

    if (s.length() == 0 || s.charAt(0) == '0') {
      return 0;
    }

    if (s.length() == 1) {
      return 1;
    }

    int fix = (s.length() == 2 ? 1 : 0);

    int ways;

    if (s.charAt(0) == '1' || (s.charAt(0) == '2' && Integer.parseInt("" + s.charAt(1)) < 7)) {
      ways = numDecodings(s.substring(1)) + numDecodings(s.substring(2)) + fix;
      map.put(s, ways);
      return ways;
    }

    ways = numDecodings(s.substring(1));
    map.put(s, ways);
    return ways;
  }