Simple Java O(1) space and O(n) time solution.


  • 0
    L

    We don't need an entire array.. just last and lastButOne is enough.

    public int noOfWays(String s) {
       if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
       // base case for dp[0]
       int lastButOne = 1;
       //base case for dp[1]
       int last = 1;
       for (int i = 2; i<= s.length(); i++) {
           int temp = last;
           if (s.charAt(i-1) == '0') last = 0;
    
           if (s.charAt(i-2) == '1' 
                 || (s.charAt(i-2) == '2' && s.charAt(i-1) < '7')) {
               last += lastButOne;
           } 
           lastButOne = temp;
       }
       return last;
    }
    

Log in to reply
 

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