Welcome to Subscribe On Youtube
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 writtend-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 digits2
through9
.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