394、字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
题解
明显的树形结构。
栈
class Solution{
// 遍历字符串的下标,方便脱离循环单独处理
int ptr;
public String decodeString(String s) {
// 双向链表结构的栈
LinkedList<String> stk = new LinkedList<String>();
ptr = 0;
while (ptr < s.length()) {
// 获取当前字符
char cur = s.charAt(ptr);
// 遇到数字
if(Character.isDigit(cur)) {
String digits = getDigits(s);
stk.addLast(digits);
} else if (Character.isLetter(cur) || cur == '[') {
// 这里简单处理，'['肯定在栈底
stk.addLast(String.valueOf(s.charAt(ptr++)));
} else {// 一定是 ']'
++ptr;
LinkedList<String> sub = new LinkedList<>();
// 栈顶不是'[', 将内部字符串取出
while(!"[".equals(stk.peekLast())) {
sub.addLast(stk.removeLast());
}
Collections.reverse(sub);
// '[' out stack
stk.removeLast();
// get times of str
int repTime = Integer.parseInt(stk.removeLast());
StringBuilder t = new StringBuilder();
// get the str pair to the repTime
String o = getString(sub);
// 构造重复的字符串
while (repTime-- > 0) {
t.append(o);
}
// add into stack
stk.addLast(t.toString());
}
}
return getString(stk);
}
// 处理大数字
private String getDigits(String s) {
StringBuilder ret = new StringBuilder();
while (Character.isDigit(s.charAt(ptr))) {
ret.append(s.charAt(ptr++));
}
return ret.toString();
}
public String getString(LinkedList<String> v) {
StringBuilder ret = new StringBuilder();
for (String s: v) {
ret.append(s);
}
return ret.toString();
}
}
- 另一个实现
class Solution {
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int multi = 0;
// 数字栈
LinkedList<Integer> stack_multi = new LinkedList<>();
// 字符串栈
LinkedList<String> stack_res = new LinkedList<>();
for(Character c : s.toCharArray()) {
if(c == '[') {
// 当前的重复次数结束
stack_multi.addLast(multi);
// 将之前的字符串加入栈
stack_res.addLast(res.toString());
// 重新初始化
multi = 0;
res = new StringBuilder();
}
else if(c == ']') {
// 将重复字符串构造成原字符串
StringBuilder tmp = new StringBuilder();
int cur_multi = stack_multi.removeLast();
for(int i = 0; i < cur_multi; i++) tmp.append(res);
// 更新res
res = new StringBuilder(stack_res.removeLast() + tmp);
}
else if(c >= '0' && c <= '9') {
multi = multi * 10 + Integer.parseInt(c + "");
} else {
res.append(c);
}
}
return res.toString();
}
}
// 作者：jyd
// 链接：https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
递归处理
利用编译原理的知识，词法分析。
class Solution {
String src;
int ptr;
public String decodeString(String s) {
src = s;
ptr = 0;
return getString();
}
private String getString() {
if (ptr == src.length() || src.charAt(ptr) == ']') {
return "";
}
char cur = src.charAt(ptr);
int repTime = 1;
String ret = "";
if (Character.isDigit(cur)) {
// 解析数字
repTime = getDigits();
// jump '['
++ptr;
// 递归 解析String
String str = getString();
// jump ']'
++ptr;
while(repTime-- > 0) {
ret += str;
}
} else if (Character.isLetter(cur)) {
ret = String.valueOf(src.charAt(ptr++));
}
return ret + getString();
}
private int getDigits() {
int ret = 0;
while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
ret = ret * 10 + src.charAt(ptr++) - '0';
}
return ret;
}
}
- 另一个实现
class Solution {
public String decodeString(String s) {
return dfs(s, 0)[0];
}
// 由于递归的特性不用担心不同层级之间的数据被覆盖
private String[] dfs(String s, int i) {
StringBuilder res = new StringBuilder();
int multi = 0;
// 继续循环
while(i < s.length()) {
if(s.charAt(i) >= '0' && s.charAt(i) <= '9') 、
// 更新数字
multi = multi * 10 + Integer.parseInt(String.valueOf(s.charAt(i)));
else if(s.charAt(i) == '[') {
// 递归
String[] tmp = dfs(s, i + 1);
i = Integer.parseInt(tmp[0]);
while(multi > 0) {
res.append(tmp[1]);
multi--;
}
}
else if(s.charAt(i) == ']') {
// 结束
return new String[] { String.valueOf(i), res.toString() };
}
else {
res.append(String.valueOf(s.charAt(i)));
}
i++;
}
return new String[] { res.toString() };
}
}
// 作者：jyd
// 链接：https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
