leecode 394. 字符串解码 java版本

2020-05-29 17:07:06

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

作者：jyd
链接：https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
来源：力扣（LeetCode）

解法一：辅助栈法
本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

算法流程：

构建辅助栈 stack， 遍历字符串 s 中每个字符 c；

1.当 c 为数字时，将数字字符转化为数字 cnt，用于后续倍数计算；
2.当 c 为字母时，在 str 尾部添加 c；
3.当 c 为 [ 时，将当前 cnt 和 str 入栈，并分别置空置 ：
　　记录此 [ 前的临时结果 str 至栈，用于发现对应 ] 后的拼接操作；
　　记录此 [ 前的倍数 cnt 至栈，用于发现对应 ] 后，获取 cnt × [...] 字符串。
　　进入到新 [ 后，str 和 cnt 重新记录。
4.当 c 为 ] 时，stack 出栈，拼接字符串 str= last_res + cur_multi * res，其中:
　　last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a；
　　cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2。
返回字符串 str。
复杂度分析：

时间复杂度 O(N)O(N)，一次遍历 s；
空间复杂度 O(N)O(N)，辅助栈在极端情况下需要线性空间，例如 2[2[2[a]]]。

java算法是根据 他们分析才写出来的 ,做算法题，个人感觉最重要的是每次做了题收获是什么，这题的难点就是【】的嵌套，最初的想法是先用stack来做，可以解决单层嵌套，

后来看他们都在用LinkedList 双向链表，来解决可能更简洁一些，相信我题刷的多了也能有自己的更好的思路吧··加油！！    2020-05-29   18:22:31 

import java.util.*;
class Solution {
    public String decodeString(String s) {
        LinkedList<Integer> stacki = new LinkedList<>();// 
        LinkedList<String> stacks = new LinkedList<>();//存放【之前的字符串
        StringBuilder str = new StringBuilder();   
        int cnt =0;
        for(Character c : s.toCharArray()){
            if(c<='z'&&c>='a'||c<='Z'&&c>='A'){
                str.append(c+"");
            }
            if(c<='9'&&c>='0'){
                cnt = cnt*10 + c-'0';
            }
            if(c=='['){
                stacks.addLast(str.toString());//把str存入栈
                stacki.addLast(cnt);//把cnt存入栈
                str=new StringBuilder();
                cnt=0;
            }
            if(c==']'){
                int n = stacki.removeLast();
                StringBuilder st = new StringBuilder();
                for(int j=0;j<n;j++) st.append(str);
                str= new StringBuilder(stacks.removeLast() + st) ;// 3[a2[c]] 的a + cc
            }
        }
        return str.toString();
    }
}

这是之前写的代码，边界条件太多，思路混淆，不知怎么下手

import java.util.*;
class Solution {
    public String decodeString(String s) {
        Stack stack=new Stack();
        if(s.length()<1) return "";
        char[] c = s.toCharArray();
        String res = "";
        String rest = "";
        for(int i=0;i<c.length;i++){
            if(c[i]=='['){
                res = res+rest;
                rest="";
            }
            if(c[i]!=']'){
                if(c[i]<'z'&&c[i]>'a'||c[i]<'Z'&&c[i]>'A'&&rest.length()>1){
                    for(Character ch : rest.toCharArray()){
                        stack.push(ch);
                    }
                    rest="";}
                stack.push(c[i]);
            }
            if(c[i]==']'){
                while((char)stack.peek()!='['){
                    rest= stack.pop()+rest;
                }
                stack.pop();
                int cnt = Integer.parseInt(stack.pop().toString());
                int j=1;
                while(!stack.isEmpty()&&(char)stack.peek()>='0'
                &&(char)stack.peek()<='9'){
                    j *=10;
                    cnt = cnt+Integer.parseInt(stack.pop().toString())*j;
                }
                String str = rest;
                while(cnt>1){
                    rest = str + rest;
                    cnt--;
                }
            }
        }
        if(rest.length()>1)res = res+rest;
        String t ="";
        while(!stack.isEmpty()){
            t = stack.pop()+t;
        }
            res = res + t;
        return res;
    }
}

 心痛···，代码写的很糟糕。