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
;
- 是数字,则将总长度缩小等量倍
- 如果整除了,观察是否是数字:
- 是数字,则将总长度缩小等量倍
size = size / S[i]
; - 不是数字,则找到答案。
- 是数字,则将总长度缩小等量倍
代码
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var decodeAtIndex = function (s, k) {
let size = 0;
const isDigit = (str) => str >= '0' && str <= '9';
for (let item of s) {
if (isDigit(item)) size *= Number(item);
else size++;
}
for (let i = s.length - 1; i >= 0; i--) {
k %= size;
if (k != 0) {
if (isDigit(s[i])) {
size = size / Number(s[i]);
} else {
size--;
}
} else {
if (isDigit(s[i])) {
size = size / Number(s[i]);
} else {
return s[i];
}
}
}
};