作者:Grey
原文地址:
题目描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例 1:
输入:s = "3[a]2[bc]"
输出:"aaabcbc"
示例 2:
输入:s = "3[a2[c]]"
输出:"accaccacc"
示例 3:
输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"
示例 4:
输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"
题目链接见:LeetCode 394. Decode String
主要思路
定义递归函数
String[] p(char[] str, int n, int from)
递归含义表示,str 字符串从 from 开始一直到结尾或者右边括号生成的信息返回,返回值是一个长度为 2 的数组,例如
2[abc]3[cd]ef
这个字符串,递归函数在执行过程中,遇到第一个右括号的时候,就会结算出两个信息,
第一个信息:之前处理过的字符串是什么;
第二个信息:处理到了哪个位置。
所以,在经历第一次递归过程后,返回
String[] res
其中
res[0] = "abcabc"; // 第一次遇到],进行结算生成的字符串
res[1] = "5" // 处理到了第五个位置,即第一个]出现的位置
继续递归
res[0] = "abcabccdcdcd"; // 第二次遇到],进行结算生成的字符串,注:这里要拼接上上一次递归的"abcabc"
res[1] = "10" // 处理到了第十个位置,即第二个]出现的位置
继续,后续没有]了,所以一直到字符串最后,得到最终的结果
res[0] = "abcabccdcdcdef"; // 处理到了终止位置,结算之前拼接的字符串和最后遗留字符串拼接的最终结果
res[1] = "12"; // 处理到了终止位置
完整代码如下
class Solution {
public static String decodeString(String s) {
char[] str = s.toCharArray();
int len = str.length;
return p(str, len, 0)[0];
}
private static String[] p(char[] str, int n, int from) {
StringBuilder sb = new StringBuilder();
int pre = 0;
int i = from;
while (i != n && str[i] != ']') {
if (Character.isLowerCase(str[i]) || Character.isUpperCase(str[i])) {
// 字母
sb.append(str[i++]);
} else if (Character.isDigit(str[i])) {
// 数字
pre = pre * 10 + Integer.parseInt(String.valueOf(str[i++]));
} else if ('[' == str[i]) {
// 左括号
String[] bra = p(str, n, i + 1);
sb.append(build(pre, bra[0]));
pre = 0;
i = Integer.parseInt(bra[1]) + 1;
}
}
return new String[] {sb.toString(), String.valueOf(i)};
}
private static String build(int pre, String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < pre; i++) {
sb.append(s);
}
return sb.toString();
}
}
代码说明
主要看p
函数的while
循环部分,其中i != n && str[i] != ']'
就是控制每次递归只处理除了结尾位置和]位置的其他位置,遇到结尾或者]直接返回一次结算结果。
while
中的三个分支也比较直白,对于字母的话,直接append
就可以,对于数字,要处理一个简单的边界条件,即数字不一定是单个整数,可能是多位数,比如334[abc]
,对于[
,就可以结算这个[
匹配的右括号之间的内容:
// 得到与其匹配的右括号之间的内容
String[] bra = p(str, n, i + 1);
sb.append(build(pre, bra[0]));
pre = 0;
// 去下一个位置匹配
i = Integer.parseInt(bra[1]) + 1;