理解字符串游戏中第 K 个字符（逐步解析） - LeetCode 3304

Source: Dev.to

问题概述

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串

word = "a"

给定一个正整数 k。

Bob 不断让 Alice 永久执行以下操作：

将 word 中的每个字符替换为其在英文字母表中的下一个字符，并将生成的新字符串追加到原来的 word 后面。

操作示例

• "c" → "cd"
• "zb" → "zbac"

在进行足够多次操作后，使得 word 的长度至少为 k，返回 word 中第 k 个字符的值。

示例 1

输入: k = 5
输出: "b"

解释

word = "a"
第 1 次操作: 生成 "b"   → word = "ab"
第 2 次操作: 生成 "bc"  → word = "abbc"
第 3 次操作: 生成 "bccd"→ word = "abbcbccd"

第 5 个字符是 'b'。

示例 2

输入: k = 10
输出: "c"

约束条件

1 ≤ k ≤ 500

每次操作将字符串转换为

new_word = old_word + shifted(old_word)

其中 shifted(old_word) 表示每个字符向后移动一个字母（'a' → 'b'，…，'z' → 'a'）。
长度每一步都会翻倍：1 → 2 → 4 → 8 → 16 → …。
我们必须在不构建完整字符串的情况下得到第 k 个字符。

---

🧠 关键洞察

在每个阶段

S(n) = S(n‑1) + shifted(S(n‑1))

• 前半段 → 前一步的字符串 S(n‑1)
• 后半段 → shifted(S(n‑1))

因此对于任意索引 k：

• 若 k 位于前半段，则字符与前一步第 k 位相同。
• 若 k 位于后半段，则映射到前一步的 (k – half) 位置，然后将得到的字符向后移动 +1（模 26）。

---

✅ 递归实现（Java）

public class Solution {
    public char KthCharacter(int k) {
        return solve(k);
    }

    private char solve(int k) {
        if (k == 1) return 'a';

        // Find the smallest power of two ≥ k
        int length = 1;
        while (length > 1;    // half = length / 2

        // k is in the second half → recurse on the mirrored index
        char prev = solve(k - half);
        // shift by one position in the alphabet (wrap around at 'z')
        return (char)('a' + (prev - 'a' + 1) % 26);
    }
}

递归在 k == 1 时停止，返回基字符 'a'。
每次进入后半段时，我们都会对字符进行一次字母位移。

---

🔍 逐步示例（k = 6）

回溯过程

• solve(2): 'a' 向后移位 → 'b'
• solve(6): 'b' 向后移位 → 'c'

结果: 'c'

---

🧠 内存中的运行情况

k = 6 时的调用栈：

solve(6)
  → solve(2)
      → solve(1)

当递归回溯时，每一次从后半段的调用返回都会增加一次字母位移，最终得到目标字符。

---

⏱ 时间与空间复杂度

• 时间: O(log k) – 每一步递归将问题规模减半。
• 空间: O(log k) – 递归栈的深度。

---

🔥 最终要点

我们从不构造完整的字符串。通过不断缩小 k 并统计落在后半段的次数，就可以用一个简单的分治递归（或等价的迭代实现）计算所需字符。该方法的运行时间为对数级，且仅使用对数级的辅助空间。