Write a function that reverses characters in (possibly nested) parentheses in the input string. Input strings will always be well-formed with matching ()
s.
inputString = "(bar)"
, the output should besolution(inputString) = "rab"
inputString = "foo(bar)baz"
, the output should besolution(inputString) = "foorabbaz"
inputString = "foo(bar)baz(blim)"
, the output should besolution(inputString) = "foorabbazmilb"
inputString = "foo(bar(baz))blim"
, the output should be solution(inputString) = "foobazrabblim"
."foo(bar(baz))blim"
becomes "foo(barzab)blim"
and then "foobazrabblim"
.[execution time limit] 4 seconds (py3)
[input] string inputString
A string consisting of lowercase English letters and the characters (
and )
. It is guaranteed that all parentheses in inputString
form a regular bracket sequence.
Guaranteed constraints:
0 ≤ inputString.length ≤ 50
.
Return inputString
, with all the characters that were in parentheses reversed.
import re
def solution(inputString):
start,end=[],[]
for i, s in enumerate(inputString):
if s=="(":
start.append(i)
elif s==")":
end.append(i)
if end:
s, e=start.pop(), end.pop()
old=inputString[s+1:e]
new=inputString[s+1:e][::-1]
inputString=inputString.replace(old,new)
return re.sub('[\(\)]', "",inputString)
🔵 Variables
start
: queue that contains indexs of "("
.
end
: queue that contains indexs of ")"
.
🔴 Steps
s
is "("
, append current index to start
.s
is ")"
, append current indext to end
. end
is not empty, it means you found character in paranthesis, so you reverse the substring. The right pair for end[-1]
is start[-1]
def solution(s):
for i in range(len(s)):
if s[i] == "(":
start = i
if s[i] == ")":
end = i
return solution(s[:start] + s[start+1:end][::-1] + s[end+1:])
return s
Solving the problem with recursion. YES, Now I see using recursion is more readable and cleaner.
References