[LeetCode] 880. Decoded String at Index

[grandyang]

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 2through 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.

这道题给了我们一个加码后的字符串，其实就是一种特殊的压缩方式，里面的数字代表前面所有的字符串重复的次数，又给了一个坐标K，让我们返回还原后的字符串中K位置的子串，其实就是一个字符，但是返回类型非要是字符串。博主最开始做的时候，没有认真读题，将压缩方式搞错了两个地方，首先博主以为多个数字相连的话要拼成个多位数，但实际上是分开的，比如例子2中的 ha22，第一个2是将 ha 重复两次，第二个2是将 haha 重复两次。博主犯的另一个错误是以为只重复之前的字符串部分，比如 a2b3，博主以为后面的3只是将b重复三次，其实是将前面的 a2b 重复三次。不认真审题的代价是惨重的，被 OJ 批的体无完肤。现在既然已经弄清楚了题意，就来想想如何解题吧。这道题是主要是参考了大神lee215的帖子，现在很少能看到史蒂芬大神的帖子了，在后史蒂芬时代，lee215 大神独自撑起了一片天空，有时候题既是大神出的，最高分解法还是大神写的，不得不使人无比崇敬。

怒吹一波后回到题目，大家最容易想到的方法就是直接按规律还原字符串呗，将还原后的字符串保存出来，这样就可以利用K来直接访问了。这种方法博主连试都不愿意试的，OJ 是有尊严的，不甩你个 Time Limited Exceeded，也得来个 Memory Limited Exceeded 吧。保存解码后的整个字符串是不现实的，但是我们又必须要知道原字符串的坐标信息，那么唯一的选择就是记录解码后字符串的长度，比如 ha22，当遍历到a的时候，此时计数器为2，表示当前解码到的位置长度为2，当遇到第一个2的时候，用当前的计数器的值乘以这个数字，即 2x2=4，说明此时解码后的字符串长度为4，当再遍历到最后一个2的时候，同样的操作，用当前计数器的值乘以这个数字，即 4x2=8，则最终的解码后的字符串长度为8。这种操作是可以统计出解码后字符串的长度的，但是我们没有必要统计整个的长度，因为题目只让找第K个位置的字符，那么我们只需要解码到计数器 cnt 刚好大于等于K的时候就可以停止了。当 cnt 大于等于 K 的时候，现在的i位置不一定是所求，我们得往前找，找到那个符合题意的第K个字符。所以需要从i位置往前遍历，当 S[i] 是数字的时候，此时的处理就是跟之前反过来了，之前我们遇到数字，都是乘以计数器 cnt，此时我们应该用计数器除以这个数字，同时K应该对缩小后的 cnt 取余。还是拿例子2来说，当遍历完最后一个2时，此时计数器为8，大于 K=5 了，所以需要往前遍历，那么 cnt 除以2之后变为了4，此时用K对4取余，得到1。然后再往前遍历，还是2，用 cnt 除以2之后变为了2，此时 K=1 对2取余，还是1。此时再往前，遍历到字母a，此时发现 K=1 不能整除 cnt=2，则 cnt 自减1，因为还要往前走。那么当到达字母h时，此时 K=1 终于可以整除 cnt=1 了，则当前的 S[i] 即为所求，参见代码如下：

解法一：

class Solution {
public:
    string decodeAtIndex(string S, int K) {
        long i = 0, cnt = 0;
        for (; cnt < K; ++i) {
            cnt = isdigit(S[i]) ? cnt * (S[i] - '0') : (cnt + 1);
        }
        while (i--) {
            if (isdigit(S[i])) {
                cnt /= (S[i] - '0');
                K %= cnt;
            } else {
                if (K % cnt == 0) return string(1, S[i]);
                --cnt;
            }
        }
        return "grandyang";
    }
};

我们也可以使用递归来做，其实思路都是一样的，还是需要一个长整型的计数器 cnt，然后遍历原字符串S，当 S[i] 是字母的时候，且自增1后的 cnt 等于K了，说明正好找了第K个字符，直接转为字符串返回即可。否则遇到数字的话，还是要乘以计数器 cnt，若大于等于K的话，则调用递归函数，注意这里的S可以用 [0, i) 之间的子串代替，可以省些空间，当然用S也是可以的。K的话比较 tricky，因为这里 cnt 乘以了一个数字（大于1）才能大于等于K，所以当前的 cnt 一定是小于K的，那么此时就有 cnt 是否能整除K两种情况，当 cnt 不能整除K时，比如当 cnt=2，K=5 时，就是例子2中的情况，我们用K对 cnt 取余，得到1来带入递归。但是当 cnt 可以整除K时，比如当 cnt=2，K=4 时，若直接取余，会得到0，直接带入0肯定时不对的，因为题目中说了K是从1开始的，所以我们应该带入的是 cnt 本身，那么两种情况合为一个表达式就是 (K-1)%cnt + 1。若 cnt 小于K，则乘以当前数字即可，参见代码如下：
解法二：

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

Github 同步地址:

#880

参考资料：

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

https://leetcode.com/problems/decoded-string-at-index/discuss/157156/15-lines-clear-code

https://leetcode.com/problems/decoded-string-at-index/discuss/156747/C%2B%2BPython-O(N)-Time-O(1)-Space

LeetCode All in One 题目讲解汇总(持续更新中...)