-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDecode_Ways.java
More file actions
215 lines (172 loc) · 5.67 KB
/
Decode_Ways.java
File metadata and controls
215 lines (172 loc) · 5.67 KB
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using
the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of
ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
public class Solution {
public int numDecodings(String s) {
if(s==null || s.length()==0 || s.charAt(0)=='0')
return 0;
if(s.length()==1)
return 1;
int[] res = new int[s.length()];
res[0] = 1;
res[1] = check(s.charAt(1)) + check(s.charAt(0), s.charAt(1));
for(int i=2; i<s.length(); i++) {
if(check(s.charAt(i))==1)
res[i] = res[i-1];
if(check(s.charAt(i-1), s.charAt(i))==1)
res[i] += res[i-2];
if(res[i]==0)
return 0;
}
return res[s.length()-1];
}
public int check(char a) {
return a=='0' ? 0 : 1;
}
public int check(char a, char b) {
return (a=='1' || (a=='2' && b<='6')) ? 1:0;
}
}
////////////////////////////////////////////////////////////////////////
// DP. Similar as "[LeetCode] Climbing Stairs, Solution". Just add some logic
// to compare character.
// Transformation function as:
// Count[i] = Count[i-1] if S[i-1] is a valid char
// or = Count[i-1]+ Count[i-2] if S[i-1] and S[i-2] together is
// still a valid char.
public class Solution {
public int numDecodings(String s) {
if(s==null || s.length()==0)
return 0;
if(s.length()==1)
return check(s.charAt(0));
int fn = 0;
int fn_1 = check(s.charAt(0))*check(s.charAt(1)) +
check(s.charAt(0), s.charAt(1));
int fn_2 = check(s.charAt(0));
for(int i=2; i<s.length(); i++) {
if(check(s.charAt(i))==1)
fn += fn_1;
if(check(s.charAt(i-1), s.charAt(i))==1)
fn += fn_2;
if(fn==0)
return 0;
fn_2 = fn_1;
fn_1 = fn;
fn = 0;
}
return fn_1;
}
public int check(char a) {
return a=='0' ? 0:1;
}
public int check(char a, char b) {
return (a=='1' || (a=='2' && b<='6')) ? 1:0;
}
}
////////////////////////////////////////////////////////////////////////
/*
In this problem, you should consider many cases, and some of them are tricky.
1. If there is one digit, then it's obvious. If the digit is not equal to 0,
we have only one way to decode. If the digit is 0, we have no ways to decode.
2. If the number has two digits. You should consider
10: 1 way,
11-19 : 2 ways,
20: 1 way,
21-26: 2 ways,
27-29: 1 way
30,40,50,...,90: 0 way
31-39, 41-49,...,91-99: 1 way
3. If the number has len>=3 digits or more, the number is
1) the first digit starts with 0,
decodeWays=0;
2) the first two digits are from 11 to 19 or 21 to 26
decodeWays(x)=decodeWays(1 digit after x) + decodeWays(2 digits after x)
3) the first two digits are others
decodeWays(x)=decodeWays(1 digit after x)
After considering these trivial cases, you can start coding. But, keep in mind
that the recursion call is very expensive. I tried the first time using
recursion, then the time limit exceeded.
Then I use DP to store the intermediate decodeWays. Keeping these values,
recursion is avoided.
*/
public class Solution {
public int numDecodings(String s) {
if(s.length()<1)
return 0;
char[] str = s.toCharArray();
int[] decodeWays = new int[str.length];
int last = str.length - 1;
if(str[last]-'0'==0)
decodeWays[last] = 0;
else
decodeWays[last] = 1;
if(last>=1) {
if(str[last-1]-'0'>2) {
if(str[last]-'0'==0)
decodeWays[last-1]=0;
else
decodeWays[last-1]=1;
} else if(str[last-1]-'0'==2) {
if(str[last]-'0'>6)
decodeWays[last-1]=1;
else if(str[last]-'0'==0)
decodeWays[last-1]=1;
else
decodeWays[last-1]=2;
} else if(str[last-1]-'0'==1) {
if(str[last]-'0'==0)
decodeWays[last-1]=1;
else
decodeWays[last-1]=2;
} else {
decodeWays[last-1]=0;
}
}
if(last>=2) {
for(int i=last-2;i>=0;i--) {
if(str[i]-'0'==0)
decodeWays[i]=0;
else {
int ways=0;
if(str[i]-'0'<2||(str[i]-'0'==2 && str[i+1]-'0'<=6))
ways=1;
decodeWays[i]=decodeWays[i+1]+ways*decodeWays[i+2];
}
}
}
return decodeWays[0];
}
}
////////////////////////////////////////////////////////////////////////
public class Solution {
public int numDecodings(String s) {
if(s.length()==0)
return 0;
int[] hist = new int[2];
hist[0] = 1;
hist[1] = 1;
for(int i=0; i<s.length(); i++) {
int temp = 0;
if(s.charAt(i)!='0')
temp += hist[1];
if(i>0) {
int a = Integer.parseInt(s.substring(i-1, i+1));
if(s.charAt(i-1)!='0' && a<=26 && a>=1)
temp += hist[0];
}
hist[0] = hist[1];
hist[1] = temp;
}
return hist[1];
}
}