880. Decoded String at Index

🟠   🔖  栈 字符串  🔗 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)。

具体算法是：

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