LeetCode 880题解码字符串时长度比较异常致索引越界问题

核心问题 #

你遇到的异常根本原因有两个：

1. 提前终止逻辑错误：你只在每次处理单个字符前检查len(newstring) == k，但当拼接过程中长度超过k，或者最终解码后的总长度仍小于k时，不会做任何处理，直接访问newstring[k-1]必然越界。
2. 暴力构建字符串的局限性：这种方法在k很大时会导致内存溢出或超时，不符合题目要求的高效解法。

针对你的测试用例s="ha22", k=15，实际执行流程是：
处理完所有字符后，解码后的字符串是"hahahaha"，长度仅为8，远小于k=15，所以访问索引14时触发IndexError。你看到的len(newstring) == k判定成立的错觉，其实是循环开头的打印语句显示的是处理当前字符前的长度，而非处理后的长度，实际并没有触发break。

正确解法（反向推导） #

不需要构建完整的解码字符串，通过反向计算定位目标字符：

class Solution(object):
    def decodeAtIndex(self, s, k):
        total_length = 0
        # 第一步：计算解码后的总长度
        for c in s:
            if c.isdigit():
                total_length *= int(c)
            else:
                total_length += 1
        
        # 第二步：从后往前遍历，缩小范围找到目标字符
        for c in reversed(s):
            k %= total_length
            if k == 0 and c.isalpha():
                return c
            if c.isdigit():
                total_length /= int(c)
            else:
                total_length -= 1
        return ""

sol = Solution()
print(sol.decodeAtIndex(s="leet2code3", k=10))  # 输出 'o'
print(sol.decodeAtIndex(s="ha22", k=15))        # 输出 'h'

解法说明 #

1. 计算总长度：遍历字符串，累加字母长度，遇到数字则将当前总长度乘以数字，得到完整解码后的长度。
2. 反向定位：从字符串末尾开始遍历：
   • 遇到数字时，总长度除以该数字（相当于还原解码前的长度），同时将k取模总长度（因为重复的字符串是相同的，k可以映射到前一次的位置）。
   • 遇到字母时，如果k等于当前总长度（或取模后为0），说明当前字母就是目标；否则总长度减1，继续往前找。

内容的提问来源于stack exchange，提问作者user22364383