LeetCode 880 - Decoded String at Index

https://leetcode.com/problems/decoded-string-at-index/

An encoded string S is given.  To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

• If the character read is a letter, that letter is written onto the tape.
• If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.

Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

Example 1:

Input: S = "leet2code3", K = 10
Output: "o"
Explanation: 
The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10th letter in the string is "o".

Example 2:

Input: S = "ha22", K = 5
Output: "h"
Explanation: 
The decoded string is "hahahaha".  The 5th letter is "h".

Example 3:

Input: S = "a2345678999999999999999", K = 1
Output: "a"
Explanation: 
The decoded string is "a" repeated 8301530446056247680 times.  The 1st letter is "a".

Note:

1. 2 <= S.length <= 100
2. S will only contain lowercase letters and digits 2 through 9.
3. S starts with a letter.
4. 1 <= K <= 10^9
5. The decoded string is guaranteed to have less than 2^63 letters

https://www.acwing.com/solution/LeetCode/content/779/
首先计算出解码后的字符串的长度 len。
然后倒序遍历字符：(1) 当前字符为小写字母，若 K == len，则说明当前字母就是索引 K，直接返回；否则 len 自减 1。(2) 当前字符为数字，则先将 len = len / S[i]，找到重复之前的长度。若 K % len == 0，则说明索引 K 是循环节的最后一个字母，则直接从 i 开始向前找到第一个字母并返回即可。否则，K = K % len。
https://blog.csdn.net/fuxuemingzhu/article/details/81977433
如果模拟题目中的操作进行解码，空间占用过大，一定会通不过。而且，题目只要求了求指定位置的字符，并没有要求所有的字符，所以全部解码没有必要。

参考了官方的解答。思路如下：

比如，对于一个解码了的字符串，appleappleappleappleappleapple，并且要求的索引K=24的话，那么结果和K=4是一样的。因为单词apple的size=5，重复了6次。所以第K个索引和第K%size个索引是一样的。

所以我们使用反向的计算，保持追踪解码字符串的size，如果解码字符串等于一个word重复了d次的时候，我们可以把K变化为K % (word.length).

算法：

首先，找出解码字符串的长度。然后，我们反向查找，保持追踪size，也就是对编码字符串S[0], S[1], ..., S[i]解码后的长度。

如果找到的是一个数字S[i]，那么意味着解码字符串S[0], S[1], ..., S[i-1]的长度应该是size / Integer(S[i])；否则应该是size-1.
https://blog.csdn.net/qq_26440803/article/details/84261151
从题目的意思来看，我们可以很容易的使用暴力破解的方式来解决，但是可以肯定的是会超时。接下来我们选择逆向思维来解题，由于该题每次碰到数字都会将前面一段字符串重复d-1次，也就是说，每次遇见数字，那么数字之前的的字符串会重复d次。那么我们这样一来我们就可以将所得的结果分成d等份，这样每个等份的结果都是一样的。

在这里还需要提到一个特性：如果一个单词的长度为n，它重复x此，那么我们在这个单词组成的字符串中，任意K与K%n的结果都一样。

举个栗子:

字符串leetleetleetleetleetleet,对于单词leet来说重复6次，我们取K=3，那么3%4与K=3的结果是一样的。利用这些特性我们可以使用逆向思维的方式，将字符串逐渐缩小范围求解，如果我们求k那么可以转换为K%n，这样一步一步我们就可以不用考虑内存，考虑时间问题。

首先我们需要先求出字符串的长度，出现数字直接做乘法，否则我们自增。

然后我们对初始字符串进行倒序遍历，由于题目的设定，我们最后一位肯定是数字，那么我们可以认为，之前的字符串重复d次，这样我们可以利用上面的特性对所求的字符串进行缩减K%n。我们所求的目标K一定在第一个重复的字符串中，以题目例子来说:

leet2code3->leetleetcodeleetleetcodeleetleetcode 缩减一下

leetleetcode k一定是在这个字符串中，因为k与k%n结果等价。

由于上述操作我们实际上是截去了一部分字符串，将重复的n次截取掉了n-1次，接下来就需要缩减size了，这对于求size是一个逆向的过程，所以我们遇见字符串就自减，遇见数字做除法。

然后重复我们之前的操作，对于k缩减为K%n，一直到满足K缩减为0，且它必须是一个字符。

当k=10，针对leetleetcode来说，K==K%10，因为此时K小于了单词的长度，所以起不到截取的目的，不能够缩小检索的范围，所以我们可以为了缩小范围，我们从后面开始遍历，对于非数字自减，这样我们就可以缩小size的范围，且不影响K，当k==size则满足我们的要求。正面检索到了我们需要的位置。

https://blog.csdn.net/zjucor/article/details/81429686
Discuss里有很简单的写法：先往右扩，扩到超过K，然后往回退

idea真的很simple，但是确实有效，其实就是个stack，看到题目应该要能想到能用stack来解的

We decode the string and N keeps the length of decoded string, until N >= K.
Then we go back from the decoding position.
If it's S[i] = d is a digit, then N = N / d before repeat and K = K % N is what we want.
If it's S[i] = c is a character, we return c if K == 0 or K == N

https://leetcode.com/articles/decoded-string-at-index/
Approach 1: Work Backwards

If we have a decoded string like appleappleappleappleappleapple and an index like K = 24, the answer is the same if K = 4.

In general, when a decoded string is equal to some word with size length repeated some number of times (such as apple with size = 5 repeated 6 times), the answer is the same for the index K as it is for the index K % size.

We can use this insight by working backwards, keeping track of the size of the decoded string. Whenever the decoded string would equal some word repeated d times, we can reduce K to K % (word.length).

Algorithm

First, find the length of the decoded string. After, we'll work backwards, keeping track of size: the length of the decoded string after parsing symbols S[0], S[1], ..., S[i].

If we see a digit S[i], it means the size of the decoded string after parsing S[0], S[1], ..., S[i-1]will be size / Integer(S[i]). Otherwise, it will be size - 1.

  public String decodeAtIndex(String S, int K) {

    long size = 0;

    int N = S.length();

    // Find size = length of decoded string

    for (int i = 0; i < N; ++i) {

      char c = S.charAt(i);

      if (Character.isDigit(c))

        size *= c - '0';

      else

        size++;

    }

    for (int i = N - 1; i >= 0; --i) {

      char c = S.charAt(i);

      K %= size;

      if (K == 0 && Character.isLetter(c))

        return Character.toString(c);

      if (Character.isDigit(c))

        size /= c - '0';

      else

        size--;

    }

    throw null;

  }

https://leetcode.com/problems/decoded-string-at-index/discuss/157390/Logical-Thinking-with-Clear-Code

Only the character in the Kth position matters rather than the whole string decoded, so we only keep track of curLength (long data type to avoid integer overflow).
Let's see the code commented, first a1, a2, then b1, b2. They are matching except that we manage K in a2, b2.
Since the result character can only be a letter rather than digit, in b2 we ought to check K. Whenever K % curLength == 0, we figure out the result.

    public String decodeAtIndex(String S, int K) {
        
        long curLength = 0;
        char c = 0;
        
        for (int i = 0; i < S.length(); i++) {
            c = S.charAt(i);
            if (Character.isDigit(c)) { \\ a1
                curLength *= c - '0';
            }
            else { \\ b1
                curLength++;
            }
        }
        
        for (int i = S.length() - 1; i >= 0; i--) {
            c = S.charAt(i);
            if (Character.isDigit(c)) { \\ a2
                curLength /= c - '0';
                K %= curLength;
            }
            else { \\ b2
                if (K == 0 || K == curLength) {
                    return "" + c;
                }
                curLength--;
            }
        }
        
        throw null;
    }

X. https://buptwc.com/2018/08/05/Leetcode-884-Decoded-String-an-Index/

1. 
   这道题是把字符串按照给定的规则展开，然后返回展开后的字符串的第K个字符，应该要怎么思考呢？
2. 我不知道大家注意到note的第5点没有，为什么他在这里突然加这么一点，告诉我们长度小于2^63，其实就是在暗示我们要用到总长度（因为我们不可能真把展开后的字符串写出来）
3. 然后这里的测试样例也有点迷惑作用，因为他故意不给出最后以字符结尾的例子，就是担心把思路直接暴露出来了，我们来看一个例子
4. S = ‘leet2code3problem’，这个字符串展开后总长度为43，’problem’是没有重复的部分，前面’leet2code3’总长度是36，那么假设此时K = 37,38,39…，43，我们可以直接得出答案。那如果K小于37呢，那么问题是不是可以转换成在S=’leet2code3’求第K个字符（多余的部分可以直接不要）
5. 当以数字结尾时，那么整个字符串就是S[:-1]的若干次重复，例如此时S=’leet2code3’的长度为36，设K=18吧，那么基本字符串的长度应该为36/3=12，那么我们要求的字符应该是第18%12=6个字符，现在问题转换成了S=’leet2code’,K=6,又变成我们第4点中分析的情况了，依次类推即可

思路：

1. 分析过程很简单明了，但是代码却不太好写，比较繁杂
2. 我们先去找S中最后一个数字的位置，然后判断K是不是处于这个数字后面的那串字符串中（关键），若是则直接返回
3. 若不是则改变S，K的值，注意了我们的总长度不能每次改变一次S重新计算一次，那样太麻烦了(不过我猜应该不会超时，因为s长度不超过100)，而是每次通过减去多余字符串的长度和除以结尾数字来改变！！！

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class Solution(object): def decodeAtIndex(self, S, K): """ :type S: str :type K: int :rtype: str """ # 先计算总长度 M = 0 for i in range(len(S)): if '1' < S[i] <= '9': M *= int(S[i]) else: M += 1 def helper(S,K,M): # 找到最后数字出现的位置 index = -1 for i in range(len(S)-1,-1,-1): if '1' < S[i] <= '9': index = i;break # 若没有数字，说明已经是最简字符串了，直接返回即可 if index == -1: return S[K-1] # 判断K是不是在数字后面的那串字符串中 if M-K < len(S)-1-index: return S[K-M-1] # 先减去多余字符串的长度，然后再除以最后数字的大小，然后调整K的大小 M -= len(S)-index-1 M //= int(S[index]) K %= M # 这里一个小问题，假如K=3，M=3，那么实际应该返回第三个字符但是这里去mod的话会是0，所以要单独处理这种情况 if K == 0: K = M return helper(S[:index],K,M) return helper(S,K,M)

X. http://hehejun.blogspot.com/2018/08/leetcodedecoded-string-at-index.html
首先我们可以从左到右遍历到第K个字符，慢慢展开字符串即可。但是这种方法显而易见是有缺点的，如果展开的字符串太长是会MLE的。时间复杂度为O(N)，但是空间复杂度可能非常大

    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 "";
    }