O(1) space Java DP solution without any exchange


  • 2
    K

    This solution is almost the same as the normal one which costs O(n) space. But the length of integer array can be reduced from n+1 to 2 by mod 2(&1 in deed).

    public class Solution {
        public int numDecodings(final String s) {
            if (s.isEmpty()) {
                return 0;
            }
    
            // count[start & 1] is the decode ways of s.substring(start)
            final int[] count = new int[2];
    
            count[(s.length() - 1) & 1] = s.charAt(s.length() - 1) > '0' ? 1 : 0;
            count[(s.length() & 1)] = 1;
    
            for (int start = s.length() - 2; start >= 0; start--) {
                if (s.charAt(start) > '0') {
                    if (s.charAt(start) == '1' || (s.charAt(start) == '2' && s.charAt(start + 1) < '7')) {
                        count[start & 1] += count[(start + 1) & 1];
                    } else {
                        count[start & 1] = count[(start + 1) & 1];
                    }
                } else {
                    count[start & 1] = 0;
                }
            }
    
            return count[0];
        }
    }

Log in to reply
 

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