Java DP


  • 0
    J
        public int numDecodings(String s) {
            if (s.length() == 0) return 0;
            if (s.length() == 1 && !s.equals("0")) return 1;
            if (s.length() == 1 && s.equals("0")) return 0;
            int[] ways = new int[s.length() + 1];
            ways[s.length()] = 1;
            ways[s.length() - 1] = s.charAt(s.length() - 1) == '0' ? 0 : 1;
            for (int i = s.length() - 2; i >= 0; i--) {
                char c = s.charAt(i);
                if (c > '2') ways[i] = ways[i + 1];
                else if (c == '1') ways[i] = ways[i + 1] + ways[i + 2];
                else if (c == '2') {
                    ways[i] = ways[i + 1];
                    if (s.charAt(i + 1) <= '6') ways[i] += ways[i + 2];
                } else if (c == '0') ways[i] = 0;
            }
            return ways[0];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.