Leetcode394 字符串解码 递归和非递归

字符串解码
https://leetcode.cn/problems/decode-string/

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: 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”

解释：这道题中，字符串的数字表示括号内的字串出现几次。字串内又可以嵌套类似的形式。

在面试，这道题有两种解法，一种是递归，另一种非递归的方式则需要栈的思想。

public class Solution {// 定义两个成员变量，表示原字符串和当前下标String src;int curIndex;@Testpublic void test() {List<String> t = Arrays.asList("3(a2(bc))");for (String s : t) {System.out.println("递归：" + decodeString1(s));System.out.println("非递归：" + decodeString2(s));}}private String decodeString1(String str) {if (str == null || str.length() == 0) {return "";}src = str;curIndex = 0;return recursive();}private String recursive() {if (curIndex == src.length() || src.charAt(curIndex) == ')') {return "";}String ret = "";int retTime = 0;char cur = src.charAt(curIndex);if (isLetter(cur)) {ret = String.valueOf(cur);++curIndex;} else if (isDigit(cur)) {retTime = getDigit();curIndex++; // skip '('String subStr = recursive();// noticecurIndex++; // skip ')'StringBuffer buf = new StringBuffer();while (retTime-- > 0) {buf.append(subStr);}ret = buf.toString();}return ret + recursive();}private int getDigit() {int ret = 0;while (isDigit(src.charAt(curIndex))) {ret = ret * 10 + (src.charAt(curIndex) - '0'); // noticecurIndex++;}return ret;}private boolean isDigit(char cur) {if (cur >= '0' && cur <= '9') {return true;}return false;}private boolean isLetter(char cur) {if ((cur >= 'a' && cur <= 'z') || (cur >= 'A' && cur <= 'Z')) {return true;}return false;}// 非递归形式private String decodeString2(String str) {if (str == null || str.length() == 0) {return "";}src = str;curIndex = 0;// 定义一个栈，存放结果LinkedList<String> stk = new LinkedList<String>();while (curIndex < src.length()) {char cur = src.charAt(curIndex);if (isDigit(cur)) {int retTime = getDigit();stk.addLast(String.valueOf(retTime));} else if (isLetter(cur) || cur == '[') {stk.addLast(String.valueOf(cur));curIndex++;} else {curIndex++; // skip ]// 定义一个临时栈，生成子串LinkedList<String> subStk = new LinkedList<String>();while (!"[".equals(stk.peekLast())) {subStk.addFirst(stk.removeLast());}String subStr = getStrFromStk(subStk); stk.removeLast(); // pop '['int retTime = Integer.valueOf(stk.removeLast());StringBuffer buf = new StringBuffer();while (retTime-- > 0) {buf.append(subStr); // 按次数重复字串}stk.addLast(buf.toString());}}return getStrFromStk(stk);}private String getStrFromStk(LinkedList<String> stk) {StringBuffer buf = new StringBuffer();for (String s : stk) {buf.append(s);}return buf.toString();}}

递归结果

非递归结果