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
|
<<-DOC
Given an encoded string, return its corresponding decoded string.
The encoding rule is: k[encoded_string],
where the encoded_string inside the square brackets is repeated exactly k times.
Note: k is guaranteed to be a positive integer.
Note that your solution should have linear complexity because this is what you will be asked during an interview.
Example
For s = "4[ab]", the output should be
decodeString(s) = "abababab";
For s = "2[b3[a]]", the output should be
decodeString(s) = "baaabaaa";
For s = "z1[y]zzz2[abc]", the output should be
decodeString(s) = "zyzzzabcabc".
Input/Output
[time limit] 4000ms (rb)
[input] string s
A string encoded as described above. It is guaranteed that:
the string consists only of digits, square brackets and lowercase English letters;
the square brackets form a regular bracket sequence;
all digits that appear in the string represent the number of times the content in the brackets that follow them repeats, i.e. k in the description above;
there are at most 20 pairs of square brackets in the given string.
Guaranteed constraints:
0 ≤ s.length ≤ 80.
[output] string
DOC
describe "#decode_string" do
REGEX = /^(\D)?(\d)\[(.*)\]$/
def decode(count, message)
if REGEX.match?(message)
x, y, z = message.scan(REGEX)[0]
"#{x}#{decode(y.to_i, z)}" * count
else
message * count
end
end
def decode_string(message)
_, x, y = message.scan(REGEX)[0]
decode(x.to_i, y)
end
def decode_string(message)
head = 0
number = []
collect = false
until head == message.length
character = message[head]
if character.match?(/\d/)
number.push(character)
else
if collect
else
number = number.join.to_i
if character == '['
collect = true
elsif character == ']'
collect = false
end
end
end
head += 1
end
end
def decode_string(message)
return message unless message.match?(/\[|\]/)
full = message.split("[", 2)
left = full[0]
middle = full[1][0...-1]
right = full[1][-1]
puts [left, middle, right].inspect
puts decode_string(middle)
middle * left.to_i
end
def decode_string(message)
n = 0
string = ""
numbers = []
strings = []
message.chars.each do |char|
if char.match?(/\d/)
n = (n * 10) + char.to_i
elsif char == '['
numbers.push(n)
n = 0
strings.push(string) unless string == ""
string = ""
elsif char == ']'
x = string * numbers.pop
puts x
#strings[-1] = x
string = strings.pop
else
string += char
end
end
puts string
puts numbers.inspect
puts strings.inspect
nil
end
def digit?(x)
x.match?(/\d/)
end
def unwind(stack)
until stack.empty?
y = stack.pop
x = stack.pop
result = y * x rescue x + y
stack.push(result)
break if stack.size == 1
end
stack[0]
end
def decode_string(message)
s, c, n = [], "", 0
message.chars.each do |x|
if digit?(x)
s.push(c) unless c == ''
c = ""
n = (n * 10) + x.to_i
elsif x == '['
s.push(n)
n = 0
elsif x == ']'
s.push(c) unless c == ''
c = ""
else
c += x
end
end
unwind(s)
end
[
{ s: "4[ab]", x: "abababab" },
{ s: "2[b3[a]]", x: "baaabaaa" },
{ s: "z1[y]zzz2[abc]", x: "zyzzzabcabc" },
#{ s: "3[a]2[bc]", x: "aaabcbc" },
#{ s: "3[a2[c]]", x: "accaccacc" },
#{ s: "2[abc]3[cd]ef", x: "abcabccdcdcdef" },
#{ s: "", x: nil },
#{ s: "codefights", x: "codefights" },
#{ s: "2[codefights]", x: "codefightscodefights" },
#{ s: "100[codefights]", x: "codefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefights" },
#{ s: "sd2[f2[e]g]i", x: "sdfeegfeegi" },
#{ s: "2[a]", x: "aa" },
#{ s: "2[a]3[b]4[c]5[d]", x: "aabbbccccddddd" },
#{ s: "2[2[b]]", x: "bbbb" },
#{ s: "2[2[2[b]]]", x: "bbbbbbbb" },
#{ s: "2[2[2[2[b]]]]", x: "bbbbbbbbbbbbbbbb" },
].each do |x|
it do
expect(decode_string(x[:s])).to eql(x[:x])
end
end
end
|
