880. Decoded String at Index
On This Page
Given an encoded string
s, the encoded string is transformed into a tape based on the following criteria:
- When a letter is encountered, it’s written on the tape.
- When a digit
dis encountered, the current content of the tape is repeated
d - 1more times.
You are required to find and return the kth letter (1-indexed) on the decoded tape.
A straightforward solution would involve constructing the entire decoded tape and then simply accessing the kth character. However, this is impractical given the constraints, as the size of the decoded string can become extremely large.
Hints & Tips
- We can work backward from the desired index k.
- It is possible to determine the sequence of characters without decoding the entire string.
Instead of trying to build the entire string, which might be vast, we can work in reverse. Given an index
k, we can backtrack through the original encoded string to determine which character would be at that position in the decoded string.
- Iterate over the encoded string to determine the length of the decoded string.
- Work backward:
- If the current character is a digit, reduce the size of the decoded string by dividing it by the digit and also adjust the k value.
- If the current character is a letter, reduce the size of the decoded string by 1. If k is equal to the size of the decoded string or k is 0, return the current character.
def decodeAtIndex(self, s: str, k: int) -> str: size = 0 # Calculate the length of the decoded string for ch in s: if ch.isdigit(): size *= int(ch) else: size += 1 for ch in reversed(s): # Work backward through the encoded string k %= size if k == 0 and ch.isalpha(): return ch if ch.isdigit(): # Adjust the size based on the current character size /= int(ch) else: size -= 1