[LeetCode]Decoded String at Index

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

	class Solution {
	public:
	string decodeAtIndex(string S, int K) {
	string pattern;
	int len = S.size();
	for(int i = 0; i < len; ++i)
	{
	if (isalpha(S[i]))
	{
	if (--K == 0)return string(1, S[i]);
	pattern += S[i];
	}
	else
	{
	long n = S[i] - '0' - 1, pLen = pattern.size(), totalLen = n * pLen;
	if (K <= totalLen)return string(1, (pattern[(K - 1) % pLen]));
	K -= totalLen;
	string buff = pattern;
	while (n--)pattern += buff;
	}
	}
	return "";
	}
	};

view raw Decoded String at Index_1.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	string decodeAtIndex(string S, int K) {
	long len = 0;
	int n = S.size();
	for(int i = 0; i < n; ++i)
	{
	if (isalpha(S[i]))++len;
	else len *= S[i] - '0';
	}
	for (int i = n - 1; i >= 0; --i)
	{
	K %= len;
	if (!K && isalpha(S[i]))return string(1, S[i]);
	if (isdigit(S[i]))len /= S[i] - '0';
	else --len;
	}
	return "";
	}
	};

view raw Decoded String at Index_2.cpp hosted with ❤ by GitHub