## Monday, August 8, 2016

[Solution]
[Solution #1]
recursion

[Solution #2]
Iterative

// recursive
class Solution {
public String decompression(String s) {
if (s == null || s.isEmpty()) {
return s;
}

StringBuilder result = new StringBuilder();

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= 'a' && c <= 'z') {
result.append(c);
}
else if (c >= '1' && c <= '9') {
StringBuilder tmp = new StringBuilder();
int xIdx = s.indexOf("x", i);
int cnt = Integer.parseInt(s.substring(i, xIdx));
i = xIdx + 2;
int openLeft = 1;
while (true) {
if (s.charAt(i) == ']') {
openLeft--;
if (openLeft == 0) {
break;
}
else {
tmp.append(s.charAt(i));
}
}
else if (s.charAt(i) == '[') {
openLeft++;
tmp.append(s.charAt(i));
}
else {
tmp.append(s.charAt(i));
}
i++;
}

String sub = decompression(tmp.toString());
for (int k = 0; k < cnt; k++) {
result.append(sub);
}
}
}

return result.toString();
}
}

// iterative stack
class Solution2 {
public String decompression(String s) {
if (s == null || s.isEmpty()) {
return s;
}

Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c != ']') {
stack.push(c);
}
else {
while (true) {
char top = stack.pop();
if (top == '[') {
break;
}
else {
}
}
stack.pop();
StringBuilder tmp = new StringBuilder();
while (stack.peek() >= '0' && stack.peek() <= '9') {
tmp.insert(0, stack.pop());
}
int cnt = Integer.parseInt(tmp.toString());

for (int i = 0; i < cnt; i++) {
for (char p : pattern) {
stack.push(p);
}
}
}
}

StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append(stack.pop());
}

return result.reverse().toString();
}
}