leetCode The first 394 topic String decoding
link ：https://leetcode-cn.com/problems/decode-string
Given an encoded string , Returns the decoded string .
The coding rule is : k[encoded_string], Represents the encoded_string Just repeat k Time . Be careful k Positive integer guaranteed .
You can think that the input string is always valid ; There are no extra spaces in the input string , And the square brackets entered always meet the format requirements .
Besides , You can assume that the raw data does not contain numbers , All numbers only indicate the number of repetitions k , For example, there is no such thing as 3a or 2[4] The input of .
Example 1：
Input ：s = "3[a]2[bc]"
Output ："aaabcbc"
Example 2：
Input ：s = "3[a2[c]]"
Output ："accaccacc"
Example 3：
Input ：s = "2[abc]3[cd]ef"
Output ："abcabccdcdcdef"
Example 4：
Input ：s = "abc3[cd]xyz"
Output ："abccdcdcdxyz"
Tips ：
1 <= s.length <= 30
s By lowercase letters 、 Numbers and square brackets '[]' form
s Guarantee is a It works The input of .
s The value range of all integers in is [1, 300]
A typical problem solved with the idea of stack
Because the order is to find first [ ] String , then [ ] The numbers in front , At first glance, it's a little late In first out means .
-------------------------
Then the problem analysis is simple .
If you encounter a number, press the stack , But the range of numbers is [1,300], So when you finally get out of the stack, you must get all the numbers out at once . But here I use to find all the numbers at once from the past , Press the numbers on the stack at once .python You can use lists to implement stack functions , So the usage is flexible .
-------------
If you encounter letters or "[", Just press the stack
--------------
If you come across ”]“ This means that there is a set of strings that need to be repeated , Then we construct the substring through the stack . With bc3[e,f,g] For example , meet "]“ You need to stack , meet ”[“ Stop the stack , The stack order is [g,f,e], Here we need to do an inversion to get [e,f,g], String "efg”, And then put "[" Out of the stack , And then 3 Out of the stack , Construct substrings efgefgefg, Then press the substring onto the stack . obtain [bc,efgefgefg].
-------------
Finally, put the elements of the stack into a string
## python3
class Solution:
def decodeString(self, s: str) -> str:
p = 0
stack = []
while p < len(s):
cur = s[p]
# print(cur)
if cur.isdigit(): ## Deal with numbers
p += 1
while s[p].isdigit():
cur += s[p]
p += 1
stack.append(int(cur))
continue # here p Has been +1 了 , There is no need to move back in the last step
elif cur.isalpha() or cur == "[": ## Handle ordinary characters and "["
stack.append(cur)
else: ## I met "]"
temp_stack = []
while stack[-1] != "[":
temp_stack .append(stack.pop())
temp_stack[:] = temp_stack[::-1] ## The stack order is opposite to the character order , Reverse
temp_str = "" ## Spell elements into strings
for i in range(len(temp_stack)):
temp_str += temp_stack[i]
x = stack.pop() # "[" Out of the stack
x = stack.pop() # Digital out of stack
temp_str = temp_str * x ## Construct substrings
stack.append(temp_str) ## Substring stack
print(stack)
p += 1
final = ""
for i in range(len(stack)):
final += stack[i]
return final
