字符串解码题目链接https://leetcode.cn/problems/decode-string/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析有一点点思路想用双栈但是最后没能实现出来。看了官方题解后的解答//方法一栈操作 //时间复杂度渐进时间复杂度为 O(S∣s∣)即 O(S)S为解码后得出的字符串长度。 //空间复杂度O(S)S为解码后得出的字符串长度。 int ptr; public String decodeString(String s) { LinkedListString stack new LinkedList(); int n s.length(); ptr 0; while(ptr n){ char cur s.charAt(ptr); //当前字符为数字 if(Character.isDigit(cur)){ String digit getDigit(s); stack.addLast(digit); } //当前字符为字母或[ else if(Character.isLetter(cur) || cur [){ stack.addLast(String.valueOf(cur)); ptr; } //当前字符为] else{ ptr; LinkedListString sub new LinkedList(); //收集子串 while(![.equals(stack.peekLast())){ sub.addLast(stack.removeLast()); } Collections.reverse(sub); //左括号出栈 stack.removeLast(); String output getString(sub); int repTime Integer.parseInt(stack.removeLast()); StringBuffer t new StringBuffer(); //构造字符串 while(repTime-- 0){ t.append(output); } //将构造好的字符串入栈 stack.addLast(t.toString()); } } return getString(stack); } public String getDigit(String s){ StringBuffer sb new StringBuffer(); while(Character.isDigit(s.charAt(ptr))){ sb.append(s.charAt(ptr)); } return sb.toString(); } public String getString(LinkedListString temp){ StringBuffer sb new StringBuffer(); for(String str : temp){ sb.append(str); } return sb.toString(); } //方法二递归 //时间复杂度渐进时间复杂度为 O(S∣s∣)即 O(S)S为解码后得出的字符串长度。 //空间复杂度O(S)S为解码后得出的字符串长度。 int ptr 0; public String decodeString(String s) { if(ptr s.length() || s.charAt(ptr) ]){ return ; } String res ; char cur s.charAt(ptr); //遇到数字开始解析数字 if(Character.isDigit(cur)){ int repTime getDigit(s); //过滤左括号 ptr; //解析括号内的字符串 String sub decodeString(s); //过滤右括号 ptr; //构造字符串 while(repTime-- 0){ res sub; } } else{ res String.valueOf(s.charAt(ptr)); } return res decodeString(s); } public int getDigit(String s){ int repTime 0; while(Character.isDigit(s.charAt(ptr))){ repTime repTime * 10 (s.charAt(ptr) - 0); } return repTime; }分析 1、方法一的解题思路用LinkedList模拟栈方便从栈底往栈顶遍历。遍历字符串s若遇到数字则获取数字并入栈若遇到字母或左括号直接入栈若遇到右括号开始收集和处理当前括号中的字符串重复此操作直到遍历完字符串s最后栈中从栈底到栈顶的字符串拼接起来就是解码后的字符串。此方法第一需要明确我们需要从栈底往栈顶遍历元素所以就不能直接使用封装好的栈结构只能自己模拟栈第二此方法涉及到许多API的调用我还不太熟悉这些API第三当出现数字时可能有连续多个数字字符组成一个数字。 2、方法二的解题思路采用递归方法构造子串。如果当前位置为数字位那么后面一定包含一个用方括号表示的字符串即属于这种情况k[…] 我们先解析出这个数字然后递归构造括号中的子串最后根据数字构造出解析后的子串我们把 k[…] 解析结束后再次调用递归函数解析右括号右边的内容。总结本题主要有两种解题方法分别为栈操作、递归。思路不难想到但实现起来较为复杂细节较多涉及许多字符和字符串相关的API建议多练习熟能生巧。
071字符串解码
字符串解码题目链接https://leetcode.cn/problems/decode-string/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析有一点点思路想用双栈但是最后没能实现出来。看了官方题解后的解答//方法一栈操作 //时间复杂度渐进时间复杂度为 O(S∣s∣)即 O(S)S为解码后得出的字符串长度。 //空间复杂度O(S)S为解码后得出的字符串长度。 int ptr; public String decodeString(String s) { LinkedListString stack new LinkedList(); int n s.length(); ptr 0; while(ptr n){ char cur s.charAt(ptr); //当前字符为数字 if(Character.isDigit(cur)){ String digit getDigit(s); stack.addLast(digit); } //当前字符为字母或[ else if(Character.isLetter(cur) || cur [){ stack.addLast(String.valueOf(cur)); ptr; } //当前字符为] else{ ptr; LinkedListString sub new LinkedList(); //收集子串 while(![.equals(stack.peekLast())){ sub.addLast(stack.removeLast()); } Collections.reverse(sub); //左括号出栈 stack.removeLast(); String output getString(sub); int repTime Integer.parseInt(stack.removeLast()); StringBuffer t new StringBuffer(); //构造字符串 while(repTime-- 0){ t.append(output); } //将构造好的字符串入栈 stack.addLast(t.toString()); } } return getString(stack); } public String getDigit(String s){ StringBuffer sb new StringBuffer(); while(Character.isDigit(s.charAt(ptr))){ sb.append(s.charAt(ptr)); } return sb.toString(); } public String getString(LinkedListString temp){ StringBuffer sb new StringBuffer(); for(String str : temp){ sb.append(str); } return sb.toString(); } //方法二递归 //时间复杂度渐进时间复杂度为 O(S∣s∣)即 O(S)S为解码后得出的字符串长度。 //空间复杂度O(S)S为解码后得出的字符串长度。 int ptr 0; public String decodeString(String s) { if(ptr s.length() || s.charAt(ptr) ]){ return ; } String res ; char cur s.charAt(ptr); //遇到数字开始解析数字 if(Character.isDigit(cur)){ int repTime getDigit(s); //过滤左括号 ptr; //解析括号内的字符串 String sub decodeString(s); //过滤右括号 ptr; //构造字符串 while(repTime-- 0){ res sub; } } else{ res String.valueOf(s.charAt(ptr)); } return res decodeString(s); } public int getDigit(String s){ int repTime 0; while(Character.isDigit(s.charAt(ptr))){ repTime repTime * 10 (s.charAt(ptr) - 0); } return repTime; }分析 1、方法一的解题思路用LinkedList模拟栈方便从栈底往栈顶遍历。遍历字符串s若遇到数字则获取数字并入栈若遇到字母或左括号直接入栈若遇到右括号开始收集和处理当前括号中的字符串重复此操作直到遍历完字符串s最后栈中从栈底到栈顶的字符串拼接起来就是解码后的字符串。此方法第一需要明确我们需要从栈底往栈顶遍历元素所以就不能直接使用封装好的栈结构只能自己模拟栈第二此方法涉及到许多API的调用我还不太熟悉这些API第三当出现数字时可能有连续多个数字字符组成一个数字。 2、方法二的解题思路采用递归方法构造子串。如果当前位置为数字位那么后面一定包含一个用方括号表示的字符串即属于这种情况k[…] 我们先解析出这个数字然后递归构造括号中的子串最后根据数字构造出解析后的子串我们把 k[…] 解析结束后再次调用递归函数解析右括号右边的内容。总结本题主要有两种解题方法分别为栈操作、递归。思路不难想到但实现起来较为复杂细节较多涉及许多字符和字符串相关的API建议多练习熟能生巧。
