Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 괄호 생성


값 n이 있다고 가정합니다. n개의 여는 괄호와 닫는 괄호가 있는 모든 가능한 잘 구성된 괄호를 생성해야 합니다. 따라서 n =3의 값이면 괄호 세트는 ["()()()","()(())","(())()","(()()) ","((()))"]

이 문제를 해결하기 위해 다음 단계를 따릅니다.

  • genParenthesisRec()라는 메서드를 정의합니다. 이것은 왼쪽, 오른쪽, 임시 문자열 및 결과 배열을 사용합니다. 초기 결과 배열이 비어 있습니다.
  • genParenthesisRec 함수는 아래와 같이 작동합니다.
  • left =0이고 right :=0이면 결과에 temp를 삽입하고 반환합니다.
  • 남은 경우> 0
    • getParenthesisRec(왼쪽 – 1, 오른쪽, 온도 + "(", 결과)
  • 오른쪽> 왼쪽
    • getParenthesisRec(왼쪽, 오른쪽 – 1, 온도 + ")", 결과)

예제(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def generateParenthesis(self, n):
      """
      :type n: int
      :rtype: List[str]
      """
      result = []
      self.generateParenthesisUtil(n,n,"",result)
      return result
   def generateParenthesisUtil(self, left,right,temp,result):
      if left == 0 and right == 0:
         result.append(temp)
         return
      if left>0:
         self.generateParenthesisUtil(left-1,right,temp+'(',result)
      if right > left:
         self.generateParenthesisUtil(left, right-1, temp + ')', result)
ob = Solution()
print(ob.generateParenthesis(4))

입력

4

출력

["(((())))",
"((()()))",
"((())())",
"((()))()",
"(()(()))",
"(()()())",
"(()())()",
"(())(())",
"(())()()",
"()((()))",
"()(()())",
"()(())()",
"()()(())",
"()()()()"]