Leetcode 884 Decoded String an 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.

分析：

  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)