題目:
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.
If the character read is a digit d, the entire current tape is repeatedly written d - 1 more times in total.
Given an integer k, return the kth letter (1-indexed) in the decoded string.
| class Solution: def decodeAtIndex(self, s: str, k: int) -> str: length = 0 i = 0 # find the length that is less than k while length < k: if s[i].isdigit(): length *= int(s[i]) else: length += 1 i += 1 # Reverse Traversal for j in range(i - 1, -1, -1): char = s[j] if char.isdigit(): # While it's reverse so the total can be devided by it length //= int(char) k %= length else: # When k is used up or k == length return the curr char if k == 0 or k == length: return char length -= 1 # TIP: Reverse Traversal(To avoid create an acutal decoded string) # Reverse: if encountered Letter: len - 1; if encountered Digit: len / 2 # Time Complexity = O(n); Space Complexity = O(1) sol = Solution() print(sol.decodeAtIndex("leet2code3", 10)) print(sol.decodeAtIndex("ha22", 5)) print(sol.decodeAtIndex("a2345678999999999999999", 1)) |
Space Complexity: O(1)
逆向操作好猛喔
根本不用創一個又臭又長的字串
阿不然example 3根本印不完
是說暑假到現在也是練了一些
只是都沒po上來
在思考要不要一邊複習一邊補上來 :P
