I thought O(n) running time will be an acceptable solution, but for some reason I'm getting "Time Limit Exceed".


  • 0
    Q
    class Solution {
        public int numDecodings(String s) {
            long[] decodeWaysAtAllIdx = new long[s.length()];
            int divisor = 1000000007;
            for (int idx = 0; idx < s.length(); idx++) {
                long decodeWaysAtIdx = calculateDecodeWay(s, idx, decodeWaysAtAllIdx);
                decodeWaysAtAllIdx[idx] = decodeWaysAtIdx % divisor;
            }
            return (int) decodeWaysAtAllIdx[s.length() - 1];
        }
        
        private long calculateDecodeWay(String s, int idx, long[] decodeWaysAtAllIdx) {
            int multiplier1;
            int multiplier2;
            if (idx == 0)
                return getSingleCodeMultiplier(s.substring(0, 1));
            if (idx == 1) {
                multiplier1 = getSingleCodeMultiplier(s.substring(1,2));
                multiplier2 = getJoinCodeMultiplier(s.substring(0, 2));
                return decodeWaysAtAllIdx[idx-1] * multiplier1 + 1 * multiplier2;
            }
            
            multiplier1 = getSingleCodeMultiplier(s.substring(idx,idx+1));
            multiplier2 = getJoinCodeMultiplier(s.substring(idx-1, idx+1));
            long decodeWaysFirstHalf = decodeWaysAtAllIdx[idx-1] * multiplier1;
            long decodeWaysSecondHalf = decodeWaysAtAllIdx[idx-2] * multiplier2;
            return  decodeWaysFirstHalf + decodeWaysSecondHalf;     
        }
        
        private int getJoinCodeMultiplier(String joinCode) {
            if(joinCode.matches("\\*\\*"))
                return 15;
            if(joinCode.matches("\\*[0-6]"))
                return 2;
            if(joinCode.matches("\\*[7-9]") || joinCode.matches("[1][0-9]") || joinCode.matches("[2][0-6]"))
                return 1;
            if(joinCode.matches("1\\*"))
                return 9;
            if(joinCode.matches("2\\*"))
                return 6;
            return 0;
        }
        
        private int getSingleCodeMultiplier(String code) {
            if(code.matches("\\*"))
                return 9;
            if(code.matches("[1-9]"))
                return 1;
            return 0;
        }
    }
    

    I ran the test case which failed during submission in "Run Code" and it finishes around 300ms: (The test case is too long for the post, its the one with 100,002 characters)

    UPDATE: After playing with it a bit, it turns out that the String.matches() call are contributing a bit to the running time. Submission was successful after replacing those String.matches() calls.


Log in to reply
 

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