leetcode 394. Decode String | 394. 字符串解码（用栈做表达式转换）

r囧r小猫 2022-09-01 08:38 156阅读 0赞

## 题目 ##

[https://leetcode.com/problems/decode-string/][https_leetcode.com_problems_decode-string]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

思路来源于中缀表达式，具体过程见下图草稿。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
逻辑上不难，这题的槽点在 StringBuilder 以及 String 以及 char 以及 int 的类型转换过程中，显得代码很臃肿。

class Solution { 
        public String decodeString(String s) { 
            Stack<StringBuilder> stack = new Stack<>();
            int num = 0;
            for (int i = 0; i < s.length(); i++) { 
                char c = s.charAt(i);
                if (c >= '0' && c <= '9') { 
                    num *= 10;
                    num += (c - '0');
                } else if (c == '[' || c >= 'a' && c <= 'z') { 
                    if (c == '[') { 
                        StringBuilder sb = new StringBuilder();
                        sb.append(num);
                        stack.push(sb);
                        num = 0;
                    }
                    StringBuilder sb = new StringBuilder();
                    sb.append(c);
                    stack.push(sb);
                } else {  // c=']'
                    StringBuilder sub = new StringBuilder();
                    StringBuilder pop = stack.pop();
                    while (!pop.toString().equals("[")) { 
                        sub.insert(0, pop);
                        pop = stack.pop();
                    }
                    int n = Integer.parseInt(stack.pop().toString()); // repeat times
                    String repeat = sub.toString().repeat(n);
                    StringBuilder sb = new StringBuilder();
                    sb.append(repeat);
                    stack.push(sb);
                }
            }
            StringBuilder res = new StringBuilder();
            while (!stack.isEmpty()) { 
                res.insert(0, stack.pop());
            }
            return res.toString();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_decode-string]: https://leetcode.com/problems/decode-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/12c86239f08444b3b42f0408b3a8de86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/3283a878f26943a0a7f150149c00930b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/150c14918bc74a1ea3da8cbe7298f1ee.png