394. Decode String
Given an encoded string, return its 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]
.
Example 1:
Input: s = "3[a]2[bc]" Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]" Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef"
Example 4:
Input: s = "abc3[cd]xyz" Output: "abccdcdcdxyz"
Constraints:
1 <= s.length <= 30
s
consists of lowercase English letters, digits, and square brackets'[]'
.s
is guaranteed to be a valid input.- All the integers in
s
are in the range[1, 300]
.
Rust Solution
struct Solution;
impl Solution {
fn decode(s: &[char], m: usize, i: &mut usize) -> String {
let mut res = "".to_string();
while *i < m && s[*i] != ']' {
if s[*i].is_digit(10) {
let mut n = 0;
while *i < m && s[*i].is_digit(10) {
n *= 10;
n += (s[*i] as u8 - b'0') as i32;
*i += 1;
}
*i += 1;
let t = Self::decode(s, m, i);
*i += 1;
for _ in 0..n {
res += &t;
}
} else {
res.push(s[*i]);
*i += 1;
}
}
res
}
fn decode_string(s: String) -> String {
let s: Vec<char> = s.chars().collect();
let mut i = 0;
Self::decode(&s, s.len(), &mut i)
}
}
#[test]
fn test() {
let s = "3[a]2[bc]".to_string();
let res = "aaabcbc".to_string();
assert_eq!(Solution::decode_string(s), res);
let s = "3[a2[c]]".to_string();
let res = "accaccacc".to_string();
assert_eq!(Solution::decode_string(s), res);
let s = "2[abc]3[cd]ef".to_string();
let res = "abcabccdcdcdef".to_string();
assert_eq!(Solution::decode_string(s), res);
let s = "abc3[cd]xyz".to_string();
let res = "abccdcdcdxyz".to_string();
assert_eq!(Solution::decode_string(s), res);
}
Having problems with this solution? Click here to submit an issue on github.