-
Notifications
You must be signed in to change notification settings - Fork 37
/
639 Decode Ways II
72 lines (55 loc) · 2 KB
/
639 Decode Ways II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
A message containing letters from A-Z is being encoded to numbers using the following mapping way:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:
Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
public int numDecodings(String s) {
long[] dp = new long[s.length()+1];
dp[0] = 1;
if(s.charAt(0)=='0')return 0;
if(s.charAt(0)!='0'){
dp[1] = 1;
}
if(s.charAt(0)=='*'){
dp[1] = 9;
}
for(int i=2;i<=s.length();i++){
int first = s.charAt(i-2);
int second = s.charAt(i-1);
if(second>'0'){
dp[i] += dp[i-1];
}else if(second=='*'){
dp[i] += 9*dp[i-1];
}
if(first=='*'){
if(second=='*'){
dp[i] += 15*dp[i-2];
}else if(second<='6'){
dp[i] += 2*dp[i-2];
}else{
dp[i] += dp[i-2];
}
}else if(first=='1' || first=='2'){
if(second=='*'){
if(first=='1'){
dp[i] += 9*dp[i-2];
}else{
dp[i] += 6*dp[i-2];
}
}
else if( ((first-'0')*10+(second-'0')) <= 26){
dp[i] += dp[i-2];
}
}
dp[i] %= 1000000007;
}
return (int)dp[s.length()];
}
}