[LeetCode]Decoded String at Index

首先我们可以从左到右遍历到第K个字符，慢慢展开字符串即可。但是这种方法显而易见是有缺点的，如果展开的字符串太长是会MLE的。时间复杂度为O(N)，但是空间复杂度可能非常大。代码如下：


所以我们需要寻找一个需要空间更少的方法。我们可以观察出来，对于长度为L，重复了M次的字符串，我们要在L * M的字符串中找第K(从0开始)个的话，其实就是找L中第K % L个。这样我们可以一直从最长的长度反推回去，直到找到第K个字符，同时我们也不需要存展开的字符，空间复杂度为O(1)，时间复杂度O(N)，代码如下：