880. 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 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation