Python, Straightforward with Explanation

  • 5

    Let's store the tokens like [('L', 1), ('e', 2), ('t', 1), ('c', 1), ('o', 1), ('d', 1), ('e', 1)], except in reverse. When we want a token, we pop it off the stack: t, n = 'L', 1 and return t. When there is more than one character represented, we need to put the excess back on the stack: t, n = 'e', 2 then tokens.append(('e', 1)).

    We can use a regular expression to find the tokens quickly. The pattern \D\d+ means a non-digit character, followed by 1 or more digit characters. (The + denotes a kleene plus, a wildcard character meaning "one or more of the preceding match.") All of our tokens (and only our tokens) match this pattern as desired.

    import re
    class StringIterator(object):
        def __init__(self, compressedString):
            self.tokens = []
            for token in re.findall('\D\d+', compressedString):
                self.tokens.append((token[0], int(token[1:])))
            self.tokens = self.tokens[::-1]
        def next(self):
            if not self.tokens: return ' '
            t, n = self.tokens.pop()
            if n > 1: 
                self.tokens.append((t, n - 1))
            return t
        def hasNext(self):
            return bool(self.tokens)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.