394. 字符串解码

冷不防 2022-11-27 15:56 173阅读 0赞

# 题目： #

[394. 字符串解码][394.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

1. 如果遇到 ']'，就一直在栈中找到 '['，将之间的字符连接起来，然后将 '['前面的数字作为出现次数，并将之前的 string 连接起来，再次压栈；
    2. 如果遇到数字、字母、'['就直接压栈；
    3. 最后将栈里的字符串弹出，并连接起来就ok了；

# 代码： #

import java.util.*;
    
    public class code394 { 
    
        // 1. 如果遇到 ']'，就一直在栈中找到 '['，将之间的字符连接起来，然后将 '['前面的数字作为出现次数，并将之前的 string 连接起来，再次压栈；
        // 2. 如果遇到数字、字母、'['就直接压栈；
        // 3. 最后将栈里的字符串弹出，并连接起来就ok了；
    
        public static String decodeString(String s) { 
    
            Stack<String> stack = new Stack<String>();
    
            for(int i = 0; i < s.length(); i++)
            { 
                if(s.charAt(i) == ']') // 如果遇到 ']'，就一直在栈中找到 '['，将之间的字符连接起来
                { 
                    String string = "";
                    while(!stack.peek().equals("["))
                    { 
                        string = stack.pop() + string; // stack.pop() 与 string 不能互换，因为栈是先进后出的，会反转原来的字符串
                    }
                    stack.pop();
    
                    String countString = "";
                    while((!stack.isEmpty()) && (stack.peek().charAt(0) >= '0' && stack.peek().charAt(0) <= '9'))
                    { 
                        countString = stack.pop() + countString; // 然后将 '['前面的数字作为出现次数
                    }
                    int count = Integer.parseInt(countString);
    
                    String tempString = "";
                    for(int j = 0; j < count; j++)
                    { 
                        tempString = tempString + string; // 并将之前的 string 连接起来
                    }
    
                    stack.push(tempString); // 再次压栈
                }
                else // 如果遇到数字、字母、'['就直接压栈
                { 
                    String str = String.valueOf(s.charAt(i));
                    stack.push(str);
                }
            }
    
            String res = "";
            while(!stack.isEmpty())
            { 
                res = stack.pop() + res; // 最后将栈里的字符串弹出，并连接起来
            }
            return res;
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext())
            { 
                String s = sc.next();
                String res = decodeString(s);
                System.out.println(res);
                System.out.println();
            }
        }
    }

# 参考： #

1.  [字符串解码][Link 1]
2.  [字符串解码（辅助栈法 / 递归法，清晰图解）][Link 2]
3.  [题解C++，栈][C]
4.  [C++ 递归/分治/双百][C_]
5.  [外层的先等等，把内层的解决了再和你连线][Link 3]
6.  [执行用时 : 0 ms , 在所有 C++ 提交中击败了 100.00% 的用户 内存消耗 : 8.8 MB , 在所有 C++ 提交中击败][_ 0 ms _ _ C_ _ 100.00_ _ _ _ 8.8 MB _ _ C_]
7.  [java 单栈解法逐行解释][java]
8.  [Java 辅助栈解法（有简单示意图）][Java]

[394.]: https://leetcode-cn.com/problems/decode-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/9e3e1aa47f4b4440a2421696f0bb627b.png
[Link 1]: https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/
[Link 2]: https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
[C]: https://leetcode-cn.com/problems/decode-string/solution/ti-jie-czhan-by-youlookdeliciousc/https://leetcode-cn.com/problems/decode-string/solution/ti-jie-czhan-by-youlookdeliciousc/
[C_]: https://leetcode-cn.com/problems/decode-string/solution/c-di-gui-fen-zhi-shuang-bai-by-avphn4vwuo/
[Link 3]: https://leetcode-cn.com/problems/decode-string/solution/zhan-de-ji-yi-nei-ceng-de-jie-ma-liao-bie-wang-lia/
[_ 0 ms _ _ C_ _ 100.00_ _ _ _ 8.8 MB _ _ C_]: https://leetcode-cn.com/problems/decode-string/solution/zhi-xing-yong-shi-0-ms-zai-suo-you-c-ti-jiao-zh-47/
[java]: https://leetcode-cn.com/problems/decode-string/solution/java-dan-zhan-jie-fa-zhu-xing-jie-shi-by-jerry_nju/
[Java]: https://leetcode-cn.com/problems/decode-string/solution/java-fu-zhu-zhan-jie-fa-you-jian-dan-shi-yi-tu-by-/