Clean java code: DP, O(n) time, O(1) space


  • 0
    G
    public class Solution {
        public int numDecodings(String s) {
            char[] arr = s.toCharArray();
            long a = 1, cur = 0,
                 b = arr[0] == '*' ? 9 : arr[0] == '0' ? 0 : 1;
            long mod = (long)1e9 + 7;
            for(int i=1; i<arr.length; i++) {
            	cur = ((arr[i] == '*' ? 9 : arr[i] == '0' ? 0 : 1) * b % mod + getCount(arr[i - 1], arr[i]) * a % mod) % mod;
            	a = b;
            	b = cur;
            }
            return (int)b;
        }
    
        private long getCount(char a, char b) {
        	switch(b) {
        		case '*':
            		if(a == '*') return 15;
            		else return a == '1' ? 9 : a == '2' ? 6 : 0;
            	case '0':
            		return a == '*' ? 2 : a > '0' && a < '3' ? 1 : 0;
            	default:
            		if(a == '*') return b < '7' ? 2 : 1;
            		else return a == '1' || (a == '2' && b < '7') ? 1 : 0;
    		}
        }
    }
    

Log in to reply
 

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