My code:
public class Solution {
public String decodeString(String s) {
if (s == null || s.length() == 0) {
return s;
}
Stack<Integer> count = new Stack<Integer>();
Stack<String> result = new Stack<String>();
int i = 0;
result.push("");
while (i < s.length()) {
char curr = s.charAt(i);
if (curr >= '0' && curr <= '9') {
int j = i + 1;
while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') {
j++;
}
count.push(Integer.parseInt(s.substring(i, j)));
i = j;
continue;
}
else if (curr == '[') {
result.push("");
}
else if (curr == ']') {
String temp = result.pop();
int number = count.pop();
StringBuilder ret = new StringBuilder();
for (int k = 0; k < number; k++) {
ret.append(temp);
}
result.push(result.pop() + ret.toString());
}
else {
result.push(result.pop() + curr);
}
i++;
}
return result.pop();
}
}
看答案写的。
reference:
https://discuss.leetcode.com/topic/57250/java-short-and-easy-understanding-solution-using-stack
还是很巧妙地，利用两个栈，把一个复杂的问题变得很有条理。
注意一个细节。
result 一开始 就压入了 一个 ""
我认为这个技巧很聪明。
result的定义是什么：
result.peek() 是当前位置下，上一层的string
所以当我们碰到 ']'
首先将这一层的string 拷贝多次，
然后，得把上一层的string pop 出来，和这个string连接，然后再压入栈中。
如果一开始不插一个 "", 栈就会溢出。
这也是一开始我以为他肯定有bug的原因。
很巧妙。
Anyway, Good luck, Richardo! -- 09/10/2016
