Java easy solution with O(1) space using dp idea


  • 2
    Y

    The idea is the same as dp. When we iterate through the given String and encounters a new character, to decode it, we only need the number of decode ways of substring(0,i) (stored in last1) and substring(0,i-1) (stored in last2). To save memory, we do not need a dp array to store every step.

    public int numDecodings(String s){
            if(s == null || s.length() == 0) return 0;
    
            //initialize
            int last2 = 1; // Decode ways before last two steps (substring(0,i-1))
            int last1 = s.charAt[0] == '0'? 0:1; // Decode ways before the last step (substring(0,i))
    
            for(int i = 1; i < s.length(); i++){
                int count = 0;
                //check 1 digit
                if(s.charAt(i) != '0') count += last1;
    
                //check 2 digits
                int twoDigits = (s.charAt(i-1) -'0') *10 + (s.charAt(i) - '0');
                if(twoDigits >= 10 && twoDigits <= 26) count += last2;
    
                // update last1 and last2
                last2 = last1;
                last1 = count;
            }
            return last1;
        }
    

Log in to reply
 

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