Java, straightforward solution, O(N) time, O(1) space


  • 1

    First consider the 4 cases of the current character (*, 0, 1--6, 7--9) ;

    Then consider the 4 cases of the previous character as sub-cases under each case (*, 1, 2, else);

    public class Solution {
        public int numDecodings(String s) {
            int mod = 1_000_000_007;
            if (s==null || s.length() ==0 || s.charAt(0)=='0') return 0;
            long prevprev=1, prev= s.charAt(0) == '*' ? 9 : 1; //important! prevprev = 1 not 0, since it's valid; otherwise 1* will return 9 but not 18
            for (int i=1; i<s.length(); i++){
                long count =0; //to prevent overflow
                char ch = s.charAt(i), prevCh = s.charAt(i-1);            
                if(ch == '0') {
                    if (prevCh == '1' || prevCh =='2') {
                        count = prevprev;
                    } else if (prevCh == '*') {
                        count = prevprev * 2;   
                    } else {
                        return 0;
                    }
                } else if (ch > '6' && ch != '*') {
                    count = prev; 
                    if (prevCh == '1' || prevCh == '*') {
                        count += prevprev;
                    } 
                } else if (ch == '*') {
                    count = 9*prev;
                    if (prevCh =='1' || prevCh =='*') {
                        count += prevprev * 9;
                    }
                    if (prevCh =='2' || prevCh =='*') {
                        count += prevprev * 6; //* represent 1--6,  not  0--6
                    }
                }  else {
                    count = prev;
                    if (prevCh == '1' || prevCh == '*') {
                        count += prevprev;
                    }
                    if (prevCh =='2' || prevCh =='*') {
                        count += prevprev;
                    }
                }
                prevprev = prev;
                prev = count % mod;            
            }
            return (int) prev;
        }
    }
    

Log in to reply
 

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