力扣394——字符串解码
- 2020 年 2 月 19 日
- 筆記
这道题主要涉及的是对递归和栈的理解。
原题
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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".
原题url：https://leetcode-cn.com/problems/decode-string/
解题
递归
这道题目，简单来看就是根据数字和内容，进行不断重复输出，最终得出结果。因此，递归也是最容易让人想到的。
数字代表内容需要重复的次数，[代表一次新的递归开始，]代表本次递归的结束，有点类似括号匹配这种问题。只是需要记录中间结果，以及最开始的s进过一次递归遍历后的下标位置。
基于上面的讲解，我们也就能够写出代码：
class Solution { public String decodeString(String s) { StringBuilder resultSb = new StringBuilder(); dfs(s, 0, resultSb); return resultSb.toString(); } public int dfs(String s, int index, StringBuilder resultSb) { // 需要重复的次数 int count = 0; while (index < s.length()) { char temp = s.charAt(index); // 如果是数字，则先累计进count中 if (temp >= '0' && temp <= '9') { count = count * 10 + temp - '0'; } // 遇到'['，则开始新一轮的递归 else if (temp == '[') { StringBuilder tempResult = new StringBuilder(); index = dfs(s, index + 1, tempResult); // 重复 for (int i = 0; i < count; i++) { resultSb.append(tempResult); } // count进行重置 count = 0; } // 遇到']'，结束递归 else if (temp == ']') { // 返回新的下标 return index; } // 遇到字母 else { resultSb.append(temp); } index++; } return index; } }
提交OK。
利用栈
既然有递归的写法，那么自然有不递归的写法，这就需要借助栈了。大家可以类比成计算一段普通的数学表达式，里面有括号、数字、符号运算等，所以需要两个栈，分别存储数字和运算符。
这道题目自然也是需要两个栈的，一个用来存储重复的次数，一个用来存储中间的字符串结果。判断出栈、入栈的依据，依据是[]，[代表数字和字符串都压入相应的栈，]代表需要将数字和字符串都需要从栈首压出，进行计算。
接下来看看代码：
class Solution { public String decodeString(String s) { // 存放次数的栈 Stack<Integer> countStack = new Stack<>(); // 存放字符串的栈 Stack<StringBuilder> sbStack = new Stack<>(); // 临时存储字符串的内容 StringBuilder tempSb = new StringBuilder(); // 临时存储数字的内容 int tempCount = 0; // 遍历 for(char temp : s.toCharArray()) { // 如果是数字，则先累计进tempCount中 if (temp >= '0' && temp <= '9') { tempCount = tempCount * 10 + temp - '0'; } // 遇到'['，将之前的数字和字符串放进countStack中 else if (temp == '[') { countStack.push(tempCount); tempCount = 0; sbStack.push(tempSb); tempSb = new StringBuilder(); } // 遇到']'，从countStack拿出数字 else if (temp == ']') { // 重复 StringBuilder tempResult = new StringBuilder(); int count = countStack.pop(); for (int j = 0; j < count; j++) { tempResult.append(tempSb); } // 拿出sbStack第一个 StringBuilder sb = sbStack.pop(); tempSb = sb.append(tempResult); } // 遇到字母 else { tempSb.append(temp); } } return tempSb.toString(); } }
提交OK。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要涉及的是对递归和栈的理解，有点类似数学表达式的计算，只是做一下类比即可。
