It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
As a countermeasure, it seems that a site called Let Code will take measures.
A site that trains algorithmic power that can withstand coding tests that are often done in the home.
I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 40 starting from zero "114. Flatten Binary Tree to Linked List"
I'm currently solving the Top 100 Liked Questions Medium. I solved all Easy, so if you are interested, please go to the table of contents.
Twitter I'm doing it.
The problem is, if you specify an encoded string, let's design an algorithm that returns that decoded string.
The encoding rule is k [encoded_string]. The encoding_string in square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer.
You can assume that the input string is always valid. There are no extra spaces, and the brackets are well-formed.
Furthermore, it can be assumed that the original data does not contain numbers and that the numbers correspond only to these repeat numbers k. For example, there is no input like 3a or 2 [4].
An example is as follows.
s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
class Solution:
def decodeString(self, s: str) -> str:
stack,curNum,curStr = [],0,''
for st in s:
if st == "[":
stack.append(curStr)
stack.append(curNum)
curStr = ""
curNum = 0
elif st == "]":
num = stack.pop()
preStr = stack.pop()
curStr = preStr + num*curStr
elif st.isdigit():
curNum = curNum*10 + int(st)
else:
curStr += st
return curStr
# Runtime: 20 ms, faster than 98.29% of Python3 online submissions for Decode String.
# Memory Usage: 13.9 MB, less than 5.77% of Python3 online submissions for Decode String.
I solved it using stack. I licked the element from the beginning with the for statement and changed the process according to the given element. It happens to be fast ...
It feels good, so this time it's up to here! Thank you for your hard work.
Recommended Posts