跳至主要內容

880. 索引处的解码字符串


880. 索引处的解码字符串open in new window

🟠   🔖  字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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)

具体算法是:

  • 首先顺序遍历字符串,计算解码字符串的总长度 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];
			}
		}
	}
};