leetcode/
decode_string.rs

1//! # 394. 字符串解码
2//!
3//!
4//! 难度 中等
5//!
6//! 给定一个经过编码的字符串，返回它解码后的字符串。
7//!
8//! 编码规则为: `k[encoded_string]`，表示其中方括号内部的 `encoded_string` 正好重复 `k` 次。注意 `k` 保证为正整数。
9//!
10//! 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
11//!
12//! 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 `k` ，例如不会出现像 `3a` 或 `2[4]` 的输入。
13//!
14//! ## 示例 1：
15//!
16//! ```text
17//! 输入：s = "3[a]2[bc]"
18//! 输出："aaabcbc"
19//! ```
20//!
21//! ## 示例 2：
22//! ```text
23//!
24//! 输入：s = "3[a2[c]]"
25//! 输出："accaccacc"
26//! ```
27//!
28//! ## 示例 3：
29//! ```text
30//!
31//! 输入：s = "2[abc]3[cd]ef"
32//! 输出："abcabccdcdcdef"
33//! ```
34//!
35//! ## 示例 4：
36//! ```text
37//!
38//! 输入：s = "abc3[cd]xyz"
39//! 输出："abccdcdcdxyz"
40//! ```
41//!
42//! See [leetcode](https://leetcode-cn.com/problems/decode-string/)
43
44pub struct Solution;
45
46impl Solution {
47
48    /// 递归
49    pub fn decode_string(s: String) -> String {
50        Self::decode(&mut s.chars())
51    }
52
53    // 因为题目说明「可以认为输入总是有效的」，所以这里不做有效性检查。
54    //
55    // 注意递归的回返条件：
56    //
57    // * 读取到 `]`
58    // * 或者 iter 被读取结束
59    //
60    // 递归解析过程：
61    //
62    // * 读取每个字符，
63    // * 遇到 `[` 用递归解码对应 `]` 之内的字符，repeat 之后拼接到 s 缓存，继续读取之后的字符
64    // * 遇到 `]` 说明本次递归完成，退出 iter 循环，repeat 之后返回（递归返回条件之一，另一个是读取完 iter）
65    // * 遇到数字，加入 `number` 缓存
66    // * 遇到其它字符，加入 `s` 缓存
67    fn decode<T: Iterator<Item = char>>(iter: &mut T) -> String {
68        let mut number = String::new(); // 数字缓存
69        let mut s = String::new(); // 字符缓存
70        while let Some(c) = iter.next() {
71            match c {
72                // 遇到 `[` 说明前面的数字读完了，递归解码 `]` 之前的字符，然后用数字重复
73                // 同时，清空 `number`
74                '[' => {
75                    let r = Self::decode(iter);
76                    // Call `number.drain(..)` will reset the `number` empty, because the `number` is right before `[`
77                    s.push_str(&r.repeat(number.drain(..).collect::<String>().parse::<usize>().unwrap_or(1)));
78                }
79                // 遇到 `]` 说明读完了 `[]` 里的字符，在一次递归里这里已经完成，退出 iter
80                // 循环，repeat 之后返回
81                ']' => {
82                    break;
83                }
84                // 遇到数字，加入 `number` 之后
85                '0'..='9' => {
86                    number.push(c);
87                }
88                // 遇到其它字符，加入 `s` 之后
89                c => {
90                    s.push(c);
91                }
92            }
93        }
94
95        // 本次递归读取完成，repeat 之后返回
96        s.repeat(number.parse::<usize>().unwrap_or(1))
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::Solution;
103
104    #[test]
105    fn test() {
106        let t = |s: &str| Solution::decode_string(s.into());
107        assert_eq!("", t(""));
108        assert_eq!("aaabcbc", t("3[a]2[bc]"));
109        assert_eq!("accaccacc", t("3[a2[c]]"));
110        assert_eq!("abcabccdcdcdef", t("2[abc]3[cd]ef"));
111        assert_eq!("abccdcdcdxyz", t("abc3[cd]xyz"));
112        assert_eq!("zzzyypqjkjkefjkjkefjkjkefjkjkefyypqjkjkefjkjkefjkjkefjkjkefef", t("3[z]2[2[y]pq4[2[jk]e1[f]]]ef"));
113    }
114}
leetcode/decode_string.rs

leetcode/
decode_string.rs
