An encoded string S
is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:
d
), the entire current tape is repeatedly written d-1
more times in total.Now for some encoded string S
, and an index K
, find and return the K
-th letter (1 indexed) in the decoded string.
Example 1:
Input: S = "leet2code3", K = 10 Output: "o" Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10th letter in the string is "o".
Example 2:
Input: S = "ha22", K = 5 Output: "h" Explanation: The decoded string is "hahahaha". The 5th letter is "h".
Example 3:
Input: S = "a2345678999999999999999", K = 1 Output: "a" Explanation: The decoded string is "a" repeated 8301530446056247680 times. The 1st letter is "a".
Constraints:
2 <= S.length <= 100
S
will only contain lowercase letters and digits 2
through 9
.S
starts with a letter.1 <= K <= 10^9
K
is less than or equal to the length of the decoded string.2^63
letters.struct Solution;
impl Solution {
fn decode_at_index(s: String, k: i32) -> String {
let mut k = k as u64;
let s: Vec<char> = s.chars().collect();
let n = s.len();
let mut size = 0;
for i in 0..n {
match s[i] {
'0'..='9' => {
size *= (s[i] as u8 - b'0') as u64;
}
_ => {
size += 1;
}
}
}
let mut res = "".to_string();
for i in (0..n).rev() {
k %= size;
match s[i] {
'0'..='9' => {
size /= (s[i] as u8 - b'0') as u64;
}
_ => {
if k == 0 {
res = s[i].to_string();
break;
} else {
size -= 1;
}
}
}
}
res
}
}
#[test]
fn test() {
let s = "leet2code3".to_string();
let k = 10;
let res = "o".to_string();
assert_eq!(Solution::decode_at_index(s, k), res);
}