字符串解码

Category	Difficulty	Likes	Dislikes
algorithms	Medium (56.01%)	1124	-

Tags

stack | depth-first-search

Companies

google | yelp

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

1
2
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1, 300]

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    /**
     * ## 解题思路
     * * 深度遍历
     * 
    */
    string decodeString(string s) {
        int i=0;
        return dfs(s, i);
    }

    /*
    * 递归decode
    * s: 待decode的字符串， 使用引用可避免多余的拷贝；
    * i: 当前decode的起始字符下标，需要将i值返回到调用上级，所以使用引用；
    * 返回：从i开始的decode字符串；
    */
    string dfs(string& s, int& i) {
        string res;
        int repeat = 0;
        while (i < s.length()) {
            char c = s[i++];
            if (c>='0' && c<='9') {
                repeat = 10*repeat + c-'0';
            } else if ( c == '[') {
                string subs = dfs(s, i);
                while (repeat>0) {
                    res += subs;
                    repeat--;
                }
            } else if ( c == ']' ) {
                return res;
            } else {
                res += c;
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 对于字符串 "3[a2[c]]", 从左到右依次进行解码；
    /// -                 v
    /// - aaa2[c]]
    pub fn decode_string(s: String) -> String {
        let mut stack: Vec<(String, usize)> = Vec::new();
        let (mut str, mut times) = (String::new(), 0);
        for c in s.chars() {
            match c {
                '[' => {
                    stack.push((str.clone(), times));
                    times = 0;
                    str.clear();
                }
                ']' => {
                    if let Some((last_str, this_times)) = stack.pop() {
                        str = last_str + str.repeat(this_times).as_str();
                    }
                }
                '0'..='9' => times = 10 * times + (c as u8 - b'0') as usize,
                _ => {
                    str.push(c);
                }
            }
        }

        str
    }
}
// @lc code=end

struct Solution;

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(
            Solution::decode_string("3[a]2[bc]".into()),
            "aaabcbc".to_string()
        );
        assert_eq!(
            Solution::decode_string("3[a2[c]]".into()),
            "accaccacc".to_string()
        );
        assert_eq!(
            Solution::decode_string("2[abc]3[cd]ef".into()),
            "abcabccdcdcdef".to_string()
        );
        assert_eq!(
            Solution::decode_string("abc3[cd]xyz".into()),
            "abccdcdcdxyz".to_string()
        );
    }
}

字符串解码

字符串解码

解法

相关文章：