動機
不是所有括號都要遞迴
Problem
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string]
, where the encoded_string
inside the square brackets is being repeated exactly k
times. Note that k
is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k
. For example, there won't be input like 3a
or 2[4]
.
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]efOutput: abcabccdcdcdef
Example 4:
Input: s = abc3[cd]xyzOutput: abccdcdcdxyz
Constraints:
1 <= s.length <= 30
s
consists of lowercase English letters, digits, and square brackets'[]'
.s
is guaranteed to be a valid input.- All the integers in
s
are in the range[1, 300]
.
Sol
括號就直接用loop去找
class Solution:
def decodeString(self, s: str) -> str:
i,j=0,0
if not s:
return ""
elif s[i].isdigit():
while j < len(s) and s[j].isdigit():
j += 1
times = int(s[i:j])
i,j,others = j+1, j+1,0
while j < len(s) and (s[j] != ']' or others > 0):
if s[j] == '[':
others += 1
elif s[j] == ']':
others -= 1
j += 1
#print(times, s[i:j], s[j+1:])
return times*self.decodeString(s[i:j])+self.decodeString(s[j+1:])
else:
return s[i]+self.decodeString(s[i+1:])