字符串解码:给一个字符串,返回解码后的字符串。

题目

字符串解码,给一个字符串s,返回解码后的字符串。字符串编码规则为k[str]表示括号内部str字符串正好重复k次,k保证为整数,并且输入的字符串肯定符合这种编码规则不会有额外的空格。
注意事项:

  • 注意括号可能发生嵌套,例如输入字符串为3[a2[c]]应该返回accaccacc
  • 1 <= s.length <= 30
  • s由小写英文字母、数字和方括号'[]' 组成
  • s保证是一个有效的输入。左括号前肯定指明了重复次数,对于不重复的字符串不会用括号将它括住。
  • s中所有整数的取值范围为[1, 300]

输入输出

输入 输出
3[a]2[bc] aaabcbc
abc3[d2[e]] abcdeedeedee

初步分析

因为嵌套括号的可能性,所以这道题需要使用数据结构,一个栈保存数字代表重复的次数,一个栈保存当前需要重复拼接的字符串。

我的思路

使用List集合存储每个数字,然后没有考虑到临时字符串的存储。没有理解到这道题的核心思想:当发生嵌套括号时,需要从最内层的元素向外拼接。从内向外

题解思路

  • countStack栈存储需要重复的次数,stringStack栈存储当前的临时字符串。
  • 创建StringBuilder对象curStr为当前拼接的字符串,用于应对连续字符的情况,例如2[abc]
  • 创建整形count记录每个重复次数,例如2[a3[b]]则压栈顺序为:2--->3
  • 将目标字符串转为char数组进行遍历,依次判断每个字符情况。
  • 最终curStr是拼接完成的,解密后的字符串,返回。

关键点

第四步,遇到特定字符该做什么?
我们先假设最理想情况:e10[a]3[b]abc

//首先判断字符是数字的情况
if(Character.isDigit(ch)){
    //将字符转为对应的10进制数字,因为重复次数范围在1~300
    int count = 0;
    count = count * 10 + ch - '0';
    //但这里不能判断是否应该将count压栈,因为无法确定ch后面是否还有数字
}
//2.判断ch = '['情况
if(ch == '['){
    //匹配到左括号,肯定代表count已经固定得到了,将其压栈
    countStack.push(count);
    //因为第一个左括号前可能有未在括号内的字符串,也就是重复次数为1的字符串,所以需要将当前字符串压栈
    stringStack.push(curStr);
    //当前字符串已记录,让其恢复为空字符串
    curStr = new StringBuilder();
    //count也需要还原
    count = 0;
}
//3.判断ch是字母的情况
if(Character.isLetter(ch)){
    curStr.append(ch);
}
//4.判断ch = ']'右括号
if(ch == ']'){
    //每当匹配到右括号,算是一个终结条件,无论多少个括号嵌套,当匹配到右括号时后面一定都是右括号直到结束
    /*当前栈、curStr、count的情况
    countStack [10]
    stringStack ["e"]
    curStr  "a"
    count    0
    */
    //观察本次输入范例,我们需要在e后面拼接10个a字符
    count = countStack.pop();
    StringBuilder temp = new StringBuilder(stringStack.pop());
    for(int i=0;i<count;i++){
        temp.append(curStr);
    }
    curStr = temp;
    count = 0;
}

根据上面代码我们再分析这种情况a2[b3[c]]结果应该为abcccbccc

//第一次匹配到]
/*
    countStack [2,3] 栈顶为3
    stringStack ["a","b"] 栈顶为"b"
    curStr  "c"
    count    0
*/
//第二次匹配到]
/*
    countStack [2] 栈顶为2
    stringStack ["a"] 栈顶为"a"
    curStr  "bccc"
    count    0
*/
//第二次执行完后
curStr = "abcccbccc"

图解

代码

public class DecodeStr {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(getResult(str));
    }

    private static String getResult(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> stringStack = new Stack<>();
        //最终返回的就是他
        StringBuilder curStr = new StringBuilder();
        int count = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)){
                count = count * 10 + (c - '0');
            }else if (c == '['){
                countStack.push(count);
                stringStack.push(curStr.toString());
                curStr = new StringBuilder();
                count = 0;
            }else if (c == ']'){
                //找到了最内部的字符串,从stringStack中弹出
                StringBuilder decodedString = new StringBuilder(stringStack.pop());
                //寻找该字符串重复次数
                int repeatCount = countStack.pop();
                for (int i = 0; i < repeatCount; i++) {
                    decodedString.append(curStr);
                }
                curStr = decodedString;
            }else {
                curStr.append(c);
            }
        }
        return curStr.toString();
    }
}

热门相关:恭喜你被逮捕了   裙上之臣   戏精老公今天作死没   富贵不能吟   闺范