master
1<<-DOC
2Given an encoded string, return its corresponding decoded string.
3
4The encoding rule is: k[encoded_string],
5where the encoded_string inside the square brackets is repeated exactly k times.
6Note: k is guaranteed to be a positive integer.
7
8Note that your solution should have linear complexity because this is what you will be asked during an interview.
9
10Example
11
12For s = "4[ab]", the output should be
13
14decodeString(s) = "abababab";
15
16For s = "2[b3[a]]", the output should be
17
18decodeString(s) = "baaabaaa";
19
20For s = "z1[y]zzz2[abc]", the output should be
21
22decodeString(s) = "zyzzzabcabc".
23
24Input/Output
25
26[time limit] 4000ms (rb)
27[input] string s
28
29A string encoded as described above. It is guaranteed that:
30
31the string consists only of digits, square brackets and lowercase English letters;
32the square brackets form a regular bracket sequence;
33all 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;
34there are at most 20 pairs of square brackets in the given string.
35Guaranteed constraints:
36
370 ≤ s.length ≤ 80.
38
39[output] string
40DOC
41
42describe "#decode_string" do
43 REGEX = /^(\D)?(\d)\[(.*)\]$/
44
45 def decode(count, message)
46 if REGEX.match?(message)
47 x, y, z = message.scan(REGEX)[0]
48 "#{x}#{decode(y.to_i, z)}" * count
49 else
50 message * count
51 end
52 end
53
54 def decode_string(message)
55 _, x, y = message.scan(REGEX)[0]
56 decode(x.to_i, y)
57 end
58
59 def decode_string(message)
60 head = 0
61 number = []
62 collect = false
63
64 until head == message.length
65 character = message[head]
66 if character.match?(/\d/)
67 number.push(character)
68 else
69 if collect
70 else
71 number = number.join.to_i
72 if character == '['
73 collect = true
74 elsif character == ']'
75 collect = false
76 end
77 end
78 end
79 head += 1
80 end
81 end
82
83 def decode_string(message)
84 return message unless message.match?(/\[|\]/)
85
86 full = message.split("[", 2)
87 left = full[0]
88 middle = full[1][0...-1]
89 right = full[1][-1]
90
91 puts [left, middle, right].inspect
92 puts decode_string(middle)
93
94 middle * left.to_i
95 end
96
97 def decode_string(message)
98 n = 0
99 string = ""
100 numbers = []
101 strings = []
102 message.chars.each do |char|
103 if char.match?(/\d/)
104 n = (n * 10) + char.to_i
105 elsif char == '['
106 numbers.push(n)
107 n = 0
108 strings.push(string) unless string == ""
109 string = ""
110 elsif char == ']'
111 x = string * numbers.pop
112 puts x
113 #strings[-1] = x
114 string = strings.pop
115 else
116 string += char
117 end
118 end
119 puts string
120 puts numbers.inspect
121 puts strings.inspect
122 nil
123 end
124
125 def digit?(x)
126 x.match?(/\d/)
127 end
128
129 def unwind(stack)
130 until stack.empty?
131 y = stack.pop
132 x = stack.pop
133 result = y * x rescue x + y
134 stack.push(result)
135 break if stack.size == 1
136 end
137 stack[0]
138 end
139
140 def decode_string(message)
141 s, c, n = [], "", 0
142 message.chars.each do |x|
143 if digit?(x)
144 s.push(c) unless c == ''
145 c = ""
146 n = (n * 10) + x.to_i
147 elsif x == '['
148 s.push(n)
149 n = 0
150 elsif x == ']'
151 s.push(c) unless c == ''
152 c = ""
153 else
154 c += x
155 end
156 end
157 unwind(s)
158 end
159
160 [
161 { s: "4[ab]", x: "abababab" },
162 { s: "2[b3[a]]", x: "baaabaaa" },
163 { s: "z1[y]zzz2[abc]", x: "zyzzzabcabc" },
164 #{ s: "3[a]2[bc]", x: "aaabcbc" },
165 #{ s: "3[a2[c]]", x: "accaccacc" },
166 #{ s: "2[abc]3[cd]ef", x: "abcabccdcdcdef" },
167 #{ s: "", x: nil },
168 #{ s: "codefights", x: "codefights" },
169 #{ s: "2[codefights]", x: "codefightscodefights" },
170 #{ s: "100[codefights]", x: "codefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefightscodefights" },
171 #{ s: "sd2[f2[e]g]i", x: "sdfeegfeegi" },
172 #{ s: "2[a]", x: "aa" },
173 #{ s: "2[a]3[b]4[c]5[d]", x: "aabbbccccddddd" },
174 #{ s: "2[2[b]]", x: "bbbb" },
175 #{ s: "2[2[2[b]]]", x: "bbbbbbbb" },
176 #{ s: "2[2[2[2[b]]]]", x: "bbbbbbbbbbbbbbbb" },
177 ].each do |x|
178 it do
179 expect(decode_string(x[:s])).to eql(x[:x])
180 end
181 end
182end