字符串解码问题
字符串解码问题
作者: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;
更多
相关文章
- 一个 DevOps 面试小宝典
- 使用 Scrapy + Selenium 爬取动态渲染的页面
- 推荐系统遇上深度学习(一四一)-[快手]移动端实时短视频推荐
- 统一、灵活、全面,这个好用的语义分割开源库全面升级啦
- MySQL事务还能这么理解?这回我知道怎么应付面试官了
- MMPose 1.0:优雅而强大的姿态估计算法框架
- 模型压缩库 MMRazor 全面升级,更灵活、自动
- MMRotate 全面升级,新增 BoxType 设计
- Java里面 根据一个字符串 计算他的hash 值(工具类)md5散列的方式计算hash值
- 【面试】揭秘面试背后的那点真实
- 【网络层】流量控制VS拥塞控制、路由器功能、SDN控制平面
- 【网络层】IP组播(多播)、硬件组播、IGMP、组播路由选择协议、移动IP、路由器详解、路由表和路由转发
- 技术硬实力,你应该这样和面试官聊Dubbo
- 技术硬实力,这样去面试你肯定会过
- 为什么阿里巴巴会这么重视技术面试呢?
- 广和通重磅发布最新5G Sub-6及毫米波模组FX170(W)!
- 学习ASP.NET Core Blazor编程系列二十二——登录(1)
- 学习ASP.NET Core Blazor编程系列二十一——数据刷新
- 学习ASP.NET Core Blazor编程系列二十——文件上传(完)
- 学习ASP.NET Core Blazor编程系列十九——文件上传(下)