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

• ``````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.

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