[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 sform 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 : 괄호가 끝나는 부분의 인덱스를 기록하는 변수입니다.

괄호 사이에 위치한 문자열을 거꾸로 배치하고, 나머지는 그대로 유지하는 문제입니다.

이러한 문제는 괄호가 하나인 경우에는 쉽게 해결이 가능하지만, 괄호가 여러개 존재할 때에는 예외가 발생할 수 있기 때문에 고려해주어야 합니다.

재귀함수를 사용하여 현재까지의 괄호 반영사항을 저장하고, 그 이후에 만나는 괄호들을 처리해주는 방식으로 문제 해결이 가능합니다.

만약, 더 이상 괄호가 없다면 현재까지의 변경 내역을 반환합니다.