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
|
<<-DOC
A top secret message containing uppercase letters from 'A' to 'Z' has been encoded as numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
You are an FBI agent and you need to determine the total number of ways that the message can be decoded.
Since the answer could be very large, take it modulo 10^9 + 7.
Example
For message = "123", the output should be
mapDecoding(message) = 3.
"123" can be decoded as "ABC" (1 2 3), "LC" (12 3) or "AW" (1 23), so the total number of ways is 3.
Input/Output
[time limit] 4000ms (rb)
[input] string message
A string containing only digits.
Guaranteed constraints:
0 ≤ message.length ≤ 105.
[output] integer
The total number of ways to decode the given message.
DOC
describe "map_decoding" do
<<-THINK
"abc"
|1|2|3|
1|a|b|c|
2|L|W|-|
3|-|-|-|
|1|2|3|
|2|2|1|
10122110
10|12|21|10
10|12|2|1|10
10|1|22|1|10
10|1|2|21|10
10|1|2|2|1|10
[1, 2, 3]
[1], [2, 3] [1, 2, 3]
[2], [3] [2], [3]
[3] [3]
THINK
def map_decoding(message)
puts [message].inspect
if message.size == 1
return (0..26).include?(message[0].to_i - 1) ? 1 : 0
end
count = 0
results = []
(message.size - 1).downto(0) do |i|
tail = message[i].to_i
combined = message[i-1..i].to_i
head = message[i - 1].to_i
if tail == 0
return 0 if combined < 0 || combined >= 26
results.push(combined)
else
if head >= 0 && head < 26
count += 1
results << tail
end
end
puts results.inspect
i += 1
end
modulo = (10 ** 9) + 7
count % modulo
end
def decode(chars, rest = [])
#puts [chars, rest].inspect
return chars if rest.empty?
results = []
first = rest[0]
results.push(decode([first], rest[1..rest.size]))
second = rest[1]
results.push(decode([first + second], rest[2..rest.size])) if second
results
end
def map_decoding(message)
decode([], message.chars)
end
# dp[n] = dp[n - 1] + dp[n - 2] if [x,y] <= 26
# dp[n] = dp[n - 1]
def map_decoding(message)
puts message.inspect
dp = [1]
return message[0].to_i > 0 ? 1 : 0 if message.size == 1
1.upto(message.size - 1) do |n|
x, y = message[n - 1], message[n]
z = (x + y).to_i
puts [x, y].join.inspect
if x != "0" && z <= 26
dp[n] = dp[n - 1] + dp[n - 2]
else
if y.to_i > 0
dp[n] = dp[n - 1]
else
dp[n] = 0
end
end
puts dp.inspect
end
modulo = (10 ** 9) + 7
dp.last % modulo
end
[
{ message: "123", expected: 3 },
{ message: "12", expected: 2 },
{ message: "0", expected: 0 },
{ message: "1", expected: 1 },
{ message: "11", expected: 2 },
{ message: "301", expected: 0 },
{ message: "1001", expected: 0 },
{ message: "10122110", expected: 5 },
{ message: "", expected: 1 },
{ message: "11115112112", expected: 104 },
{ message: "2871221111122261", expected: 233 },
{ message: "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211", expected: 782204094 },
].each do |x|
it do
expect(map_decoding(x[:message])).to eql(x[:expected])
end
end
end
|
