Decoded String At Index Problem


Description

LeetCode Problem 880.

You are given an encoded string s. To decode the string to a tape, the encoded string is read one character at a time and the following steps are taken:

  • If the character read is a letter, that letter is written onto the tape.
  • If the character read is a digit d, the entire current tape is repeatedly written d - 1 more times in total.

Given an integer k, return the k^th letter (1-indexed) in the decoded string.

Example 1:

1
2
3
4
Input: s = "leet2code3", k = 10
Output: "o"
Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10^th letter in the string is "o".

Example 2:

1
2
3
4
Input: s = "ha22", k = 5
Output: "h"
Explanation: The decoded string is "hahahaha".
The 5^th letter is "h".

Example 3:

1
2
3
4
Input: s = "a2345678999999999999999", k = 1
Output: "a"
Explanation: The decoded string is "a" repeated 8301530446056247680 times.
The 1^st letter is "a".

Constraints:

  • 2 <= s.length <= 100
  • s consists of lowercase English letters and digits 2 through 9.
  • s starts with a letter.
  • 1 <= k <= 10^9
  • It is guaranteed that k is less than or equal to the length of the decoded string.
  • The decoded string is guaranteed to have less than 2^63 letters.


Sample C++ Code

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
class Solution {
public:
    string decodeAtIndex(string S, int K) {
        long size = 0;
        int N = S.size();

        for (int i = 0; i < N; ++i) {
            if (isdigit(S[i]))
                size *= S[i] - '0';
            else
                size++;
        }

        for (int i = N-1; i >=0; --i) {
            K %= size;
            if (K == 0 && isalpha(S[i]))
                return (string) "" + S[i];

            if (isdigit(S[i]))
                size /= S[i] - '0';
            else
                size--;
        }
        return S.substr(K, 1);
    }
};




Related Posts

Validate Stack Sequences Problem

LeetCode 946. Given two integer arrays pushed and popped each...

Stamping The Sequence Problem

LeetCode 936. You are given two strings stamp and target....

Score Of Parentheses Problem

LeetCode 856. Given a balanced parentheses string s, return the...

Minimum Add To Make Parentheses Valid Problem

LeetCode 921. A parentheses string is valid if and only...

Maximum Width Ramp Problem

LeetCode 962. A ramp in an integer array nums is...

Decoded String At Index Problem

LeetCode 880. You are given an encoded string s. To...