给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
首先最后结果是一个字符串,[]里面是字母,[]前面的数字是[]内字母重复的次数,2[s2[aa]],[]的嵌套结果也会迭代。
可以用栈存储解决:
① 获取遍历字符串中的第一个‘】’之前的所有字符
② 获取其中一层的2[aa]的计算信息,分为2步骤,获取字符串和获取‘[’前的数字
③ 根据数字倍数将字母push到stack
④ 将所有结果从栈中取出,并返回
知识点补充:
① 字符串拆分成字符数组存储:s.toCharArray()
② 判断字符是否为字母:Character.isLetter(stack.peek())
③ 只获取栈顶信息,不取值:stack.peek(),stack.pop()是取值的
④ 判断字符是否为数字:Character.isDigit(stack.peek())
class Solution { public String decodeString(String s) { // 使用栈存储 Stack<Character> stack = new Stack<>(); // 遍历字符串数组 for(char c:s.toCharArray()){ //所有字符全部存储到栈中,除了 ] if(c != ']'){ stack.push(c); }else{ /** 1、获取字符串 */ //去除[]中的字符串, 使用StringBuilder存储字符 StringBuilder sb = new StringBuilder(); while(!stack.isEmpty() && Character.isLetter(stack.peek())){ sb.insert(0,stack.pop()); } // 取出[]中的字符串 String sub = sb.toString(); //[]中的字符串取完后,去除内层的[ stack.pop(); /** 2、获取[]前的数字 */ StringBuilder dight = new StringBuilder(); while(!stack.isEmpty() && Character.isDigit(stack.peek())){ dight.insert(0,stack.pop()); } int count = Integer.valueOf(dight.toString()); /** 3、根据数字倍数将字母push到stack */ while(count > 0){ for(char ch : sub.toCharArray()){ stack.push(ch); } count--; } } } /** 4、把所有的字母取出来 */ StringBuilder result = new StringBuilder(); while(!stack.isEmpty()){ result.insert(0,stack.pop()); } return result.toString(); } }
OK,你学肥么有~