字符串解码问题
作者： Grey
原文地址：
博客园：字符串解码问题
CSDN：字符串解码问题
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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;
更多
算法和数据结构笔记