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

2022-01-19 HGNULB 约 11 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

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

题意分析

给一个编码字符串 s，从左到右读取并按两条规则构建结果串：读到字母就把它追加到结果末尾；读到数字 d 就把当前已有的整个结果串重复 d 次（也就是长度变成原来的 d 倍）。要求返回解码后字符串中第 k 个字母（k 从 $1$ 开始计数）。

题面里的关键数字是：s 的长度不超过 $100$，k 不超过 $10^9$，而且题目明确保证解码后的字符串长度小于 $2^{63}$。这三个数字合在一起构成了最强的算法信号：$100$ 个字符里如果有几十个 9，长度会是天文数字，所以绝对不能真的把字符串构造出来；同时「小于 $2^{63}$」这句保证告诉我们，总长度可以安全地放进一个 $64$ 位有符号整数里，不需要做截断或大数运算。

第二个信号藏在「重复」这个操作的结构里。重复 d 次之后，结果串由 d 个完全相同的段拼成，因此第 k 个字符与第 k mod L 个字符相同（L 是重复前的段长）。这个周期性正是把「定位第 k 个字符」从构造问题降成计算问题的钥匙。

数字的取值范围是 $2$ 到 $9$（题目保证不会出现 0 和 1，也不会以数字开头），所以每个数字都会让长度严格变大，不存在长度不变或变小的情况——这保证了逆向还原时长度序列是严格递减的，过程必然终止。

边界上要覆盖：k = 1（取第一个字母）；k 恰好等于某一层的段长（此时 k mod L = 0，落在段的末尾而不是开头，这是最容易写错的一处）；s 全是字母没有数字（退化成直接取第 k 个字符）；连续多个数字（如 "a23"，长度连乘）。

解法：从后往前还原

核心思路

最直白的做法是照着规则构造字符串，边构造边判断长度是否达到 k，一旦达到就返回。这个做法在长度较小时能用，但 s 可以让长度膨胀到接近 $2^{63}$，内存和时间都会爆炸。即使加上「长度一旦超过 k 就停止构造」的剪枝，k 也能到 $10^9$，意味着仍要在内存里塞下十亿个字符，仍然不可接受。

瓶颈在于正向构造天然要把所有字符都实例化出来。观察重复操作的对称性：既然重复后的串由若干份完全相同的段组成，那么与其正向展开，不如反向折叠——从最终串出发，一层层撤销操作，把「第 k 个位置」不断映射回更短的串上的等价位置，直到某一层这个位置恰好由一个具体字母产生。

具体地，从右往左扫描 s，同时维护一个变量 size 表示「扫描到当前字符时，前缀 s[0..i] 解码出来的串有多长」。撤销规则如下：

当前字符是数字 d：说明这一步把长度从 size / d 放大到了 size。撤销之后段长变成 size / d，而由于新串是 d 个相同段的拼接，第 K 个位置在段内的等价位置是 K mod (size / d)。于是执行 size /= d 后紧跟 K %= size。

当前字符是字母：说明这一步把长度从 size - 1 增加到了 size，且新增的那个字符就位于末尾。如果目标位置恰好落在这个末尾字符上，答案就是它；否则撤销这次追加，size--。

于是维护的不变量是：扫描到下标 i 时，size 等于前缀 s[0..i] 解码后的长度，且 K 是「答案字符在这个前缀解码串中的位置」（采用 $0$ 基或「等于 size 表示末尾」的混合表示）。每撤销一步，问题规模严格变小，而答案字符不变。

判定条件 K == 0 || K == size 需要单独解释清楚，它是本题唯一真正绕的地方。K 初值取的是题目给的 k，是 $1$ 基的。取模之后有两种情况：如果 K 变成了 $0$，说明原来的 K 是段长的整数倍，也就是目标落在某个段的最后一个位置；如果 K 没被取模影响（或本来就等于当前 size），说明它就指向当前串的最后一个字符。而当前遇到的字母恰好是当前前缀解码串的最后一个字符，所以这两种情况下答案都是它。反过来，若 K 既不是 $0$ 也不等于 size，说明目标在更靠前的位置，撤销这个字母（size--）继续往左找。

之所以第一趟要先把总长度算出来，是因为反向撤销必须知道「当前前缀的解码长度」这个起点。第一趟正向累计时，遇到字母 size++、遇到数字 size *= d，正是解码规则的直接翻译，只是不生成任何字符。

解题步骤

第一趟从左到右扫描 s，用 long size 累计解码后的总长度：字母 size++，数字 size *= (ch - '0')。理由：反向撤销需要知道每一步的长度，而长度只能正向递推；用 long 是因为题目保证总长小于 $2^{63}$，恰好能装下，用 int 必然溢出。

把 k 拷进一个 long K。理由：后续会对 K 反复取模，虽然它始终不超过 size，但与 long 类型的 size 混合运算时保持同类型能避免隐式转换带来的意外。

第二趟从右到左扫描，下标 i 从 s.length() - 1 递减到 $0$。理由：撤销必须按操作的逆序进行，最后执行的操作要最先撤销。

遇到数字 d 时，先 size /= d，再 K %= size。理由：两句的顺序不能颠倒——size /= d 把长度还原成重复前的段长，之后 K 才能对这个段长取模；先取模会用错误的模数（放大后的长度）导致 K 完全不变，等于没撤销。由于数字保证是 $2$ 到 $9$，size 严格变小，不会出现除以零或死循环。

遇到字母时，先判断 K == 0 || K == size，成立就返回这个字母。理由：这两种情况都意味着目标位置正是当前前缀解码串的最后一个字符，也就是当前这个刚被追加的字母。判断必须在 size-- 之前做，因为此时 size 还代表「含这个字母的长度」。

不成立则 size-- 继续。理由：撤销这次追加，把问题规模缩小一位；K 不需要改变，因为它是 $1$ 基位置且目标在更前面，前缀缩短不影响它的编号。

循环结束后返回空串作为兜底。理由：题目保证 k 合法，正常情况下一定会在循环内返回；这个返回只是让编译器满意。

以 s = "leet2code3"、k = 10 走一遍。第一趟算总长：l,e,e,t 四个字母 size = 4；数字 2 使 size = 8；c,o,d,e 四个字母 size = 12；数字 3 使 size = 36。第二趟从右往左，K = 10。字符 3 是数字：size = 36 / 3 = 12，K = 10 % 12 = 10。字符 e：K(10) != 0 且 10 != 12，size 降为 $11$。字符 d：10 != 0 且 10 != 11，size 降为 $10$。字符 o：10 != 0 但 K == size == 10 成立，返回 "o"。验证一下：解码串是 "leetleetcodeleetleetcodeleetleetcode"，第 $10$ 个字符确实是 o，与期望一致——注意最后一步命中的是 K == size 这个分支，正是「目标恰好落在当前串末尾」的情形。

再走一个命中 K == 0 的用例：s = "ha22"、k = 5。第一趟：h,a 使 size = 2，两个 2 依次使 size = 4、size = 8。第二趟 K = 5。末尾 2：size = 4，K = 5 % 4 = 1。下一个 2：size = 2，K = 1 % 2 = 1。字符 a：1 != 0 且 1 != 2，size 降为 $1$。字符 h：1 != 0 但 K == size == 1，返回 "h"。解码串是 "hahahahaha"，第 $5$ 个是 h，正确。

代码实现

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$ 是编码字符串 s 的长度（不超过 $100$）。两趟线性扫描：第一趟累计长度，第二趟反向撤销，每个字符各处理一次，内部只做常数次乘除取模。与解码后的长度完全无关，这正是反向做法相对正向构造的根本优势。

空间复杂度：$O(1)$。只用了 size 和 K 两个 $64$ 位整数，以及循环下标；全程不构造任何字符串，也不用栈或数组——正向构造需要 $O(k)$ 甚至更多，两者差距是决定性的。

关键点总结

当输出规模远大于输入规模、而问题只要求其中某一个位置时，要立刻放弃正向构造，转向「从结果反推位置」。判断标志是「构造出来会爆内存但输入很短」，本题 $100$ 个字符对上 $2^{63}$ 的长度就是最极端的例子。

「重复 d 次」带来的是周期性，位置映射靠取模：第 K 个位置等价于第 K mod L 个位置（L 为一个周期的长度）。撤销时必须先把长度还原成周期长，再取模，顺序反了等于没做。

逆向撤销的正确性来自「每一步操作都可逆且信息足够」：追加字母的逆操作是长度减一，重复 d 次的逆操作是长度除以 d。设计逆向算法时先逐条写出逆操作，再确认每一步都能只靠 size 和 K 完成，就不会漏分支。

K == 0 与 K == size 是同一件事的两种表现——目标落在当前串的最后一位。前者来自取模后归零，后者来自从未被取模。用 $1$ 基编号时这两个条件必须都写，只写一个会在特定用例上漏判。

长度上界要看题目的显式保证。本题写明「解码串长度小于 $2^{63}$」，所以 long 恰好够用；没有这句保证时就得改成「长度一旦超过 k 就停止累加」的截断写法。

面试视角：字节和微软考这题的核心是能否意识到不能构造。理想的作答顺序是：先算一下最坏长度指出正向构造不可行，再点出「重复产生周期，位置可以取模折叠」，最后写两趟扫描。写完主动用 k 恰好等于段长的用例（如 "ha22"、k = 4）验证边界判定，这一步最能体现严谨性。如果被追问「不先算总长行不行」，可以答：可以改成正向累加到长度首次不小于 k 时停止，然后从那个位置往回撤销，效果相同且不依赖「小于 $2^{63}$」这条保证。

易错点总结

错误写法：真的把解码串构造出来再取第 k 个 → 用例 s = "a2222222222222222222222222222222"，k = 1 → 解码长度是 $2^{31}$ 量级，直接内存溢出或超时。

错误写法：size 用 int → 用例 s = "leet2code3" 这类还好，但 s = "a999999999" → 长度约 $3.9 \times 10^8$ 尚可，再多几个 9 就超出 int 范围变成负数，size /= d 得到负数，K %= size 结果异常，返回错误字符甚至崩溃。

错误写法：遇到数字时先 K %= size 再 size /= d → 用例 s = "leet2code3"，k = 10 → 用放大后的长度 $36$ 取模，K 仍是 $10$ 没有折叠，后续 size 与 K 的对应关系全部错位，返回错误字符。

错误写法：字母分支只判 K == 0 而漏掉 K == size → 用例 s = "ha22"，k = 5 → 折叠后 K = 1、size 降到 $1$ 时 K != 0，h 被跳过，循环走完返回空串，正确答案是 "h"。

错误写法：字母分支只判 K == size 而漏掉 K == 0 → 用例 s = "abc2"，k = 3 → 折叠后 K = 3 % 3 = 0，size = 3，K != size，c 被跳过；继续 size 降到 $2$、$1$ 都不匹配，返回空串，正确答案是 "c"。

错误写法：把 size-- 写在判断之前 → 用例 s = "abc"，k = 3 → 处理 c 时先把 size 从 $3$ 降到 $2$，再判 K(3) == size(2) 不成立，c 被漏掉，答案错误。

错误写法：把 K 当作 $0$ 基处理，初始化成 k - 1 却仍用 K == 0 || K == size 判定 → 用例 s = "abc"，k = 1 → K = 0 在处理 c 时就命中返回 "c"，正确答案是 "a"；$0$ 基表示下判定条件应改成 K == size - 1，两套编号不能混用。

错误写法：正向扫描累计长度时对数字写成 size += d 而不是 size *= d → 用例 s = "a2"，k = 2 → 总长算成 $3$ 而不是 $2$，后续所有折叠的基准全错。

错误写法：数字解析用 ch 直接参与运算而不减 '0' → 用例 s = "a2" → 用字符 '2' 的 ASCII 值 $50$ 当倍数，长度算成 $50$，取模基准完全错误。

错误写法：反向扫描时从 s.length() 开始或用 i > 0 作为条件 → 用例 s = "abc"，k = 1 → 前者第一次就下标越界；后者永远处理不到 s[0]，k = 1 的答案 a 被漏掉，返回空串。

相似题目

题目	难度	考察点
394. 字符串解码	中等	同样的重复编码规则，但要求输出完整串，可用栈正向展开，是本题的构造版对照
471. 编码最短长度的字符串	困难	反过来求最短编码，需要区间 DP 枚举重复段，考察编码与解码的对偶关系
1492. n 的第 k 个因子	中等	同为「不枚举全部只取第 K 个」，靠因子成对出现的结构跳过一半候选
1539. 第 k 个缺失的正整数	简单	用「已缺失个数」这个可计算量直接定位第 K 项，同样避免构造完整序列
726. 原子的数量	困难	括号带乘数因子的解析，考察嵌套倍数的累乘与合并，与本题的乘法结构同源