LeetCode 880. 索引处的解码字符串

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 微软
标签
字符串 栈

题目描述

✅ 880. 索引处的解码字符串

image-20260928225246445

image-20260928225246446

题意分析

从左到右解码：字母追加到末尾，数字 d 将整个已有字符串变成连续的 d 份。要求返回解码后第 k 个字符，下标从 1 开始。展开结果可能极长，但定位一个字符只需要知道长度和重复关系。

解法：从后往前还原

核心思路

[!blue]

先正向计算解码长度 size：字母使长度加 1，数字使长度乘 d，全程不保存展开内容。题目保证最终长度小于 $2^{63}$，而长度只会增加，所以每一步都能用 Java 的 long 或 Go 的 int64 表示。

再从编码末尾反向处理。此时 size 表示当前编码前缀解码后的长度，K 表示所求字符在这个展开前缀中的位置。撤销最后一次操作，就能把问题缩小到更短的编码前缀。

若当前字符是数字 d，它把长度为 L 的同一段复制了 d 份，因此先令 size /= d 还原 L。不同副本的相同位置是同一个字符，目标可映射为 (K - 1) % L + 1。代码用 K %= L，把余数为 0 的情况统一解释为这一段的最后一位；若 K 已经为 0，撤销重复后仍对应上一段的末尾。

若当前字符是字母，它就是当前展开串的最后一个字符。当 K == size 或 K == 0 时直接返回它；否则目标在前面的部分，删掉这个末尾字母只需令 size 减 1，目标位置不变。必须先判断再减长度，才能识别当前字母本身。

输入以字母开头，数字只会重复非空前缀，因此除法还原出的长度不会为 0。题目也保证目标位置有效，持续逆推最终一定落到某个字母，无需实际展开字符串。

解题步骤

  1. 正向扫描编码，用 64 位整数计算完整解码长度。
  2. 将目标位置 k 保存为同样宽度的 K，从编码末尾向前扫描。
  3. 遇到数字，先还原重复前长度，再令 K 对该长度取余；遇到字母，先判断目标是否在段末，否则将长度减 1。
  4. 找到目标字母立即返回。连续多个数字也能逐次撤销，每次都按当前还原出的长度重新映射位置。

代码实现

class Solution {
    public String decodeAtIndex(String s, int k) {
        long size = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (Character.isDigit(ch)) {
                size *= ch - '0';
            } else {
                size++;
            }
        }

        long K = k;

        for (int i = s.length() - 1; i >= 0; i--) {
            char ch = s.charAt(i);

            if (Character.isDigit(ch)) {
                int d = ch - '0';

                // 先还原重复前的周期长度，再映射目标位置
                size /= d;
                K %= size;
            } else {
                // 一基位置取模为零表示段末，同样由当前字母产生
                if (K == 0 || K == size) {
                    return String.valueOf(ch);
                }

                size--;
            }
        }

        return "";
    }
}

func decodeAtIndex(s string, k int) string {
    size := int64(0)
    for i := 0; i < len(s); i++ {
        ch := s[i]
        if ch >= '0' && ch <= '9' {
            size *= int64(ch - '0')
        } else {
            size++
        }
    }

    K := int64(k)
    for i := len(s) - 1; i >= 0; i-- {
        ch := s[i]
        if ch >= '0' && ch <= '9' {
            d := int64(ch - '0')
            // 先还原重复前的周期长度，再映射目标位置
            size /= d
            K %= size
        } else {
            // 一基位置取模为零表示段末，同样由当前字母产生
            if K == 0 || K == size {
                return string(ch)
            }
            size--
        }
    }

    return ""
}

复杂度分析

  • 时间复杂度：$O(N)$，N 为编码长度，与展开长度无关。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • K 为一基位置，零只是段末的特殊表示。
  • 取模的周期是还原后的段长。

易错点总结

[!yellow]

  • 先按放大后的长度取模，可能没有完成位置折叠。
  • 只检查 K 等于长度，会漏掉取模为零的末尾位置。
  • 先减少字母对应长度再判断，会错过当前末尾字符。
  • 数字重复的是整个已有前缀，不是只重复它前面的一个字母。

相似题目

题目 难度 关联与区别
394. 字符串解码 中等 原题实际展开字符串，本题只问一个下标，应先计算长度再反向映射，避免构造巨大文本。
779. 第K个语法符号 中等 同样在隐式扩展串中定位单个字符，通过上一层的位置映射消除指数规模。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/95625148
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！