LeetCode 394 - Decode String

作者 QIFAN 日期 2017-01-27
LeetCode 394 - Decode String

原题链接: 394. Decode String


题干

给定一个压缩后的字符串,返回压缩前的。

压缩形式为 k[string] ,表示 string 重复 k 次。 k > 0
假设压缩字符串都是有效的,而且只有 k 是数字,即压缩前的字符串都是字母。

思路

这是四则运算的番外版。一样的思路就是用一个 stack 存括号和 k ,另一个 stack 存压缩后的字符,当出现了一个 [] 配对后将字符展开。

for ch in input:
if (ch == '['):
push string to stringStack
push into opStack
else if ch == ']'
pop opStack
k = pop opStack
str = pop stringStack
extend str
push into stringStack
else if ch in (0,9):
push into opString
else
append str

上述思路有一个漏洞就是,一串字符后面可以直接跟数字。这个相当于一个前缀,所以在每次碰到 “[“ 是,要将前缀存入栈,而且每次展开后,展开后的字符串与前缀一起成为了后面内容的新前缀。

我只用了一个 stack ,因为所有输入都是合理的,也就是说栈里面一定是数字与字符相间隔存储的。

代码:

Stack<String> stack = new Stack<>();
public String decodeString(String s) {
if (s == null || s.length() == 0) {
return s;
}
StringBuilder res = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '[':
stack.push(res.toString()); // 前缀入栈
res = new StringBuilder(); // 初始化新的前缀
break;
case ']':
StringBuilder encode = new StringBuilder();
StringBuilder decode = new StringBuilder(stack.pop());
if (!stack.isEmpty()) {
int num = Integer.parseInt(stack.pop());
while (num-- > 0) {
decode.append(res.toString());
}
}
res = decode;
break;
default:
int j;
if (Character.isDigit(s.charAt(i))) {
j = i;
while (Character.isDigit(s.charAt(++j)));
stack.push(s.substring(i, j));
i = j - 1;
} else {
res.append(s.charAt(i));
}
break;
}
}
return res.toString();
}

这题既然是 DFS ,应该是可以用递归做的,但是麻烦的地方在于,分解的时候需要保证每一个子问题的输入都是合理的。我突然想到了,可以两个指针,因为括号一定是成对的,所以第一个括号与最后一个括号间可以看成是合理的输入,从而进行下一轮的递归。核心公式就是 结果 = 前缀 + DFS(中间) + 后缀

上面这个想法仅仅适用于全部是嵌套的情况,如果是顺序的就不能判断边界了。

又突然想到递归时先遍历一遍,判断不嵌套的各个边界(将括号存入栈,栈为空时为一个嵌套完成),然后把各个树相加就是最后结果了。这样还是挺麻烦的,应该可行不过。