Easy

题目描述

Alice 和 Bob 在玩一个游戏。最初，Alice 有一个字符串 word = “a”。

给你一个正整数 k。

现在 Bob 会要求 Alice 永远执行以下操作：

  • 通过将 word 中的每个字符更改为英文字母表中的下一个字符来生成新字符串，并将其附加到原始 word 后面。

例如，对 “c” 执行操作会生成 “cd”，对 “zb” 执行操作会生成 “zbac”。

在执行足够多的操作使 word 至少有 k 个字符后，返回 word 中第 k 个字符的值。

示例 1：

输入：k = 5
输出："b"
解释：
最初，word = "a"。我们需要执行三次操作：
- 生成的字符串是 "b"，word 变为 "ab"。
- 生成的字符串是 "bc"，word 变为 "abbc"。
- 生成的字符串是 "bccd"，word 变为 "abbcbccd"。

示例 2：

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

约束：

  • 1 <= k <= 500

提示：

  • 约束很小。通过模拟操作来构造字符串。

解题思路

这道题要求我们模拟字符串的生成过程，找到第 k 个字符。

思路分析

由于约束条件很小（k ≤ 500），我们可以直接模拟整个过程：

  1. 直接模拟：从初始字符串 “a” 开始，重复执行操作直到字符串长度至少为 k
  2. 操作规则：每次将当前字符串中的每个字符替换为字母表中的下一个字符，然后追加到原字符串后面
  3. 字符转换：‘a’ → ‘b’, ‘b’ → ‘c’, …, ‘z’ → ‘a’

优化思路

虽然直接模拟就能解决问题，但我们也可以观察到一些规律：

  • 每轮操作后，字符串长度会翻倍
  • 第 i 轮后的字符串长度为 2^i
  • 可以通过递归或位运算来优化，但由于约束很小，直接模拟是最简单的方法

推荐解法：直接模拟，因为代码简单易懂，且在给定约束下效率足够。

代码实现

class Solution {
public:
    char kthCharacter(int k) {
        string word = "a";
        
        while (word.length() < k) {
            string next = "";
            for (char c : word) {
                if (c == 'z') {
                    next += 'a';
                } else {
                    next += (c + 1);
                }
            }
            word += next;
        }
        
        return word[k - 1];
    }
};

class Solution:
    def kthCharacter(self, k: int) -> str:
        word = "a"
        
        while len(word) < k:
            next_part = ""
            for c in word:
                if c == 'z':
                    next_part += 'a'
                else:
                    next_part += chr(ord(c) + 1)
            word += next_part
        
        return word[k - 1]

public class Solution {
    public char KthCharacter(int k) {
        string word = "a";
        
        while (word.Length < k) {
            string next = "";
            foreach (char c in word) {
                if (c == 'z') {
                    next += 'a';
                } else {
                    next += (char)(c + 1);
                }
            }
            word += next;
        }
        
        return word[k - 1];
    }
}

var kthCharacter = function(k) {
    let word = "a";
    
    while (word.length < k) {
        let next = "";
        for (let char of word) {
            next += String.fromCharCode(((char.charCodeAt(0) - 97 + 1) % 26) + 97);
        }
        word += next;
    }
    
    return word[k - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(k)，最坏情况下需要生成长度为 k 的字符串
空间复杂度O(k)，存储最终生成的字符串

相关题目