880. 索引处的解码字符串

🟠   🔖  栈 字符串  🔗 力扣 LeetCode

题目

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 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 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 263 letters.

题目大意

给定一个编码字符串 S。为了找出解码字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：

• 如果所读的字符是字母，则将该字母写在磁带上。
• 如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。

现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

解题思路

由于解码后的字符串有可能超大，不仅会超时，内存也会溢出，所以不能直接暴力扫描解码。

仔细观察会发现，如果有一个像 abcdeabcdeabcdeabcdeabcdeabcde 这样的解码字符串，和一个像 k=23 这样的索引，那么如果 k=3，答案是相同的。

所以可以从后向前逆向寻找，跟踪解码字符串的大小来找出答案。每当解码的字符串等于某些单词（如 abcde）重复 n 次时，我们就可以将 k 减少到 k % ('abcde'.length)。

具体算法是：

1. 首先顺序遍历字符串，计算解码字符串的总长度 size；
2. 再从当前字符串最后一位开始遍历，用 k 对总长度求余： k %= size；
3. 如果整除了，且当前字符不是数字，则答案就是当前字符。
4. 否则，看当前字符是否是数字：
   • 是数字，则将总长度缩小等量倍 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--;
		}
	}
};