Decoded String at Index — LeetCode 880 Python Solution

The problem

You are given an encoded string s. To decode the 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.

Example

Input

s = "leet2code3", k = 10

Output

"o"

Explanation

The decoded string is "leetleetcodeleetleetcodeleetleetcode".

Python solution

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        m = 0
        for c in s:
            if c.isdigit():
                m *= int(c)
            else:
                m += 1
        for c in s[::-1]:
            k %= m
            if k == 0 and c.isalpha():
                return c
            if c.isdigit():
                m //= int(c)
            else:
                m -= 1

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 880. Decoded String at Index is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems