LeetCode : 394. Decode String 解码字符串重复复制子串

柔情只为你懂 2021-06-24 16:11 309阅读 0赞

**试题**  
Given an encoded string, return it’s decoded string.

The encoding rule is: k\[encoded\_string\], where the encoded\_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2\[4\].

Examples:

s = “3\[a\]2\[bc\]”, return “aaabcbc”.  
s = “3\[a2\[c\]\]”, return “accaccacc”.  
s = “2\[abc\]3\[cd\]ef”, return “abcabccdcdcdef”.

**代码**  
思路是利用栈，当出现\]时说明要开始进行复制操作了。  
"3\[a2\[c\]\]"为例：  
将3，\[，a，2，\[，c，分别存入栈，  
然后出现\]，将2，\[，c弹出，进行复制操作，复制完后压入栈。

class Solution {
        public String decodeString(String s) {
            if(s==null || s.length()==0) return "";
            Stack<String> de = new Stack<>();
            StringBuilder tmp = new StringBuilder();
            StringBuilder sss = new StringBuilder();
            StringBuilder merge = new StringBuilder();
            boolean flag = true;
            
            for(char c : s.toCharArray()){
                if(c=='['){
                    de.push(tmp.toString());
                    tmp.delete(0,tmp.length());
                    de.push(String.valueOf(c));
                }else if(c==']'){
                    de.push(tmp.toString());
                    tmp.delete(0,tmp.length());
                    sss.delete(0,sss.length());
                    merge.delete(0,merge.length());
                    
                    while( !de.peek().equals("[") ){
                        sss.insert(0,de.pop());
                    }
                    de.pop();
                    String re = de.pop();
                    
                    for(int i=0; i<Integer.valueOf(re); i++){
                        merge.append(sss);
                    }
                    de.push(merge.toString());
                    
                }
                else{
                    if(tmp.length()==0){
                        tmp.append(c);
                        if(c>='0' && c<='9'){
                            flag = true;
                        }else if(c>='a' && c<='z'){
                            flag = false;
                        }
                    }else if( (flag&&(c>='0' && c<='9')) || (!flag&&(c>='a' && c<='z')) ){
                        tmp.append(c);
                    }else{
                        de.push(tmp.toString());
                        tmp.delete(0,tmp.length());
                        tmp.append(c);
                        if(c>='0' && c<='9'){
                            flag = true;
                        }else if(c>='a' && c<='z'){
                            flag = false;
                        }
                    }
                }
            }
            
            StringBuilder out = new StringBuilder();
            while(!de.isEmpty()){
                out.insert(0,de.pop());
            }
            if(tmp.length()!=0) out.append(tmp);
            return out.toString();
        }
    }