O(1) space, O(N) time.in Java DP with explanation


  • 0
    N
     public int numDecodings(String s) {
       if (s == null || s.length() == 0) return 0;
         char[] charArr = s.toCharArray();
        if (charArr[0] == '0') {
            return 0;
        }
        
       //the count of decode ways
        int amount = 1;
        int preAmount = 1;
    
        //the count which last decode word in pre decode ways is single;
    
        //exmaple of pre decode ways:input is "1211"
        //current index is 4;so index is 3,decode ways:
        // 1 2 1,12 1, 1 21;
        // so 1 2 1,12 1 :last decode word is single,preSingleLast = 2;
        int preLastSingle = 1;
    
        //get the count of current char combination with the preSingleLast
        int pCount = 0;
        for (int i = 1; i < charArr.length; i++) {
            preAmount = charArr[i] == '0' ? 0 : preAmount;
            pCount = (charArr[i - 1] - '0') * 10 + charArr[i] - '0' > 26 ? 0 : preLastSingle;
    
            amount = preAmount + pCount;
            preLastSingle = preAmount;
            preAmount = amount;
        }
        return amount;
    }

Log in to reply
 

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