Solution.py

"""
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:

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

"""
class Solution(object):
    def decodeAtIndex(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        clens, clen = [], 0
        first_num_idx = -1
        for idx, ch in enumerate(S):
            res = ord(ch) - ord('0')
            if 0 <= res <= 10:
                if first_num_idx < 0:
                    first_num_idx = idx
                clen *= res
            else:
                clen += 1
            clens.append(clen)
            if clen >= K and 0 <= res <= 10:
                break
            elif clen >= K:
                return ch
        while idx >= 0:
            ch = S[idx]
            clen = clens[idx]
            idx -= 1
            res = ord(ch) - ord('0')
            # print(ch, K, clen)
            if not (0 <= res <= 10) and K == clen:
                return ch
            elif (0 <= res <= 10):
                K = K % (clens[idx])
                if K == 0:
                    K = clens[idx]
        return ch