Formatted question description: https://leetcode.ca/all/880.html

880. Decoded String at Index (Medium)

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:

If the character read is a letter, that letter is written onto the tape.
If the character read is a digit (say 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
It's 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.

Related Topics:
Stack

Solution 1.

class Solution {
    public String decodeAtIndex(String S, int K) {
        TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();
        long count = 0;
        int length = S.length();
        int index = 0;
        while (index < length && count < K) {
            char c = S.charAt(index);
            if (Character.isLetter(c))
                count++;
            else
                count *= c - '0';
            map.put(count, index);
            index++;
        }
        long position = K;
        while (!map.containsKey(position) || Character.isDigit(S.charAt(map.get(position)))) {
            long key = map.floorKey(position - 1);
            position %= key;
            if (position == 0)
                position = key;
        }
        int strIndex = map.get(position);
        char letter = S.charAt(strIndex);
        return String.valueOf(letter);
    }
}

// OJ: https://leetcode.com/problems/decoded-string-at-index/
// Time: O(S)
// Space: O(S)
class Solution {
public:
    string decodeAtIndex(string S, int K) {
        vector<tuple<string, int, long>> v;
        long N = S.size(), len = 0;
        --K;
        for (int i = 0; i < N; ) {
            string s;
            while (i < N && isalpha(S[i])) s += S[i++];
            int n = S[i++] - '0';
            len += s.size();
            v.emplace_back(s, n, len);
            len *= n;
            if (len > K) break;
        }
        for (int i = v.size() - 1; i >= 0; --i) {
            auto [s, n, len] = v[i];
            K %= len;
            if (i == 0) return string(1, s[K % s.size()]);
            else if (K >= len - s.size()) return string(1, s[K - (len - s.size())]);
        }
        return "";
    }
};

class Solution(object):
    def decodeAtIndex(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        size = 0
        for c in S:
            if c.isdigit():
                size *= int(c)
            else:
                size += 1
        
        for c in reversed(S):
            K %= size
            if K == 0 and c.isalpha():
                return c
            if c.isdigit():
                size /= int(c)
            else:
                size -= 1

880 - Decoded String at Index

880. Decoded String at Index (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

880. Decoded String at Index (Medium)

Solution 1.

All Problems

All Solutions