880. 索引处的解码字符串
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 writtend - 1
more times in total.
Given an integer k
, return thekth
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
consists of lowercase English letters and digits2
through9
.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
263
letters.
题目大意
给定一个编码字符串 S
。为了找出解码字符串并将其写入磁带,从编码字符串中每次读取一个字符,并采取以下步骤:
- 如果所读的字符是字母,则将该字母写在磁带上。
- 如果所读的字符是数字(例如
d
),则整个当前磁带总共会被重复写d-1
次。
现在,对于给定的编码字符串 S
和索引 K
,查找并返回解码字符串中的第 K
个字母。
解题思路
由于解码后的字符串有可能超大,不仅会超时,内存也会溢出,所以不能直接暴力扫描解码。
仔细观察会发现,如果有一个像 abcdeabcdeabcdeabcdeabcdeabcde
这样的解码字符串,和一个像 k=23
这样的索引,那么如果 k=3
,答案是相同的。
所以可以从后向前逆向寻找,跟踪解码字符串的大小来找出答案。每当解码的字符串等于某些单词(如 abcde
)重复 n
次时,我们就可以将 k
减少到 k % ('abcde'.length)
。
具体算法是:
- 首先顺序遍历字符串,计算解码字符串的总长度
size
; - 再从当前字符串最后一位开始遍历,用
k
对总长度求余:k %= size
; - 如果整除了,且当前字符不是数字,则答案就是当前字符。
- 否则,看当前字符是否是数字:
- 是数字,则将总长度缩小等量倍
size = size / S[i]
; - 不是数字,则总长度减一
size = size - 1
;
- 是数字,则将总长度缩小等量倍
代码
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var decodeAtIndex = function (s, k) {
const isDigit = (char) => char >= '0' && char <= '9';
let size = 0;
for (let char of s) {
if (isDigit(char)) {
size *= Number(char);
} else {
size++;
}
}
for (let i = s.length - 1; i >= 0; i--) {
k = k % size;
if (k == 0 && !isDigit(s[i])) {
return s[i];
}
if (isDigit(s[i])) {
size = Math.ceil(size / Number(s[i]));
} else {
size--;
}
}
};