[Algorithm] reverseParentheses

Problem

You have a string s that consists of English letters, punctuation marks, whitespace characters, and brackets. It is guaranteed that the parentheses in s form a regular bracket sequence.

Your task is to reverse the strings contained in each pair of matching parentheses, starting from the innermost pair. The results string should not contain any parentheses.

Example

For string s = "a(bc)de", the output should be
reverseParentheses(s) = "acbde".

Input/Output

• [input] string s

  A string consisting of English letters, punctuation marks, whitespace characters and brackets. It is guaranteed that parentheses form a regular bracket sequence.

  Constraints:
  5 ≤ s.length ≤ 55.

• [output] string

Solution

def reverseParentheses(s):
for i in range(len(s)):
if s[i] == '(':
start_idx = i
elif s[i] == ')':
end_idx = i
return reverseParentheses(s[:start_idx] + s[start_idx + 1:end_idx][::-1] + s[end_idx + 1:]
return s

*start_idx : 괄호가 시작하는 부분의 인덱스를 저장하는 변수입니다.

*end_idx : 괄호가 끝나는 부분의 인덱스를 저장하는 변수입니다.

괄호 사이에 위치한 문자를 거꾸로 배열하여 전체 문장을 반환하는 문제였습니다.

Input값에서 괄호가 한 번씩만 등장한다면 문제가 수월해지겠으나, 한 번씩만 등장한다는 전제조건은 없기 때문에 재귀 함수를 사용하여 문제를 해결하였습니다.