Java O(1) space complexity DP Solution


  • 0
    H

    Most of the DP solutions use an memo/dp array to memorize the previous decode ways results. While, in fact we don't need the whole array, the only thing we need to retrieve in calculating the decode ways in one digit is the One digit decode way and two digits decode way. So we need to know the previous variable decode ways and the variable before the previous.

        public int numDecodings(String s) {
            if(s.length()==0) return 0;
            int count=0;
            int one=1;
            int two=0;
            for(int i=s.length()-1;i>=0;i--)
            {
                if(s.charAt(i)=='0')
                {
                    two=one;
                    one=0;
                }
                else if(i+1<s.length() && (s.charAt(i)=='1'||(s.charAt(i)=='2'&&s.charAt(i+1)<='6')))
                {
                    int temp = one;
                    one+=two;
                    two=temp;
                }
                else
                {
                    two = one;
                }
            }
            return one;
        }
    

Log in to reply
 

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