괄호 생성 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance C3 사물인터넷 Facebook 구글 인튜이트 Microsoft 신탁 스포티 파이 테슬라 동네 짱
역 추적 동적 프로그래밍 월마트 글로벌 테크조회수 55

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

또한 괄호 생성 LeetCode 솔루션 – "생성하다 괄호"는 n의 값이 주어졌음을 나타냅니다. n 쌍의 괄호의 모든 조합을 생성해야 합니다.

올바른 형식의 괄호 문자열로 구성된 벡터 형식으로 답을 반환합니다.

예:

Input:  n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

설명 :

  • 모든 올바른 형식의 괄호는 다음과 같습니다.- ["((()))","(()())","(())()","()(())","()() ()”].
Input:  n = 1
Output: ["()"]

설명 :

  • 모든 올바른 형식의 괄호는 다음과 같습니다.- [“()”].

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 재귀.
  2. 무차별 대입 접근 방식은 각 인덱스에서 모든 유형의 괄호를 고려하고 다음 재귀 단계로 이동하여 이것이 올바른 형식의 괄호로 이어지는지 확인하는 것입니다. 예인 경우 문자열을 답변으로 저장하고, 그렇지 않으면 역추적합니다.
  3. 효율적인 솔루션을 위해 빈 문자열로 시작하고 n 여는 대괄호와 닫는 대괄호의 수(n 쌍을 형성해야 하기 때문에).
  4. At 재귀의 각 단계, 다음과 같은 경우가 있습니다.
    1. 기본 케이스: 여는 대괄호와 닫는 대괄호가 모두 있는 경우 n과 동일, 현재 문자열을 답변으로 저장합니다.
    2. 여는 괄호의 수가 다음과 같을 때 엄격하게 덜 n보다 이제 여는 대괄호를 배치할 수 있습니다.
    3. 닫는 괄호의 수가 다음과 같을 때 엄격하게 덜 닫는 괄호의 수보다 지금 닫는 괄호를 배치해야 합니다.
  5. 기본 케이스에 도달할 때마다 올바른 형식의 괄호인 답변에 구성된 문자열을 저장합니다.
  6. 올바른 형식의 모든 괄호를 문자열 벡터 형태로 답으로 반환합니다.

암호

괄호 생성 Leetcode C++ 솔루션:

class Solution {
public:
    vector<string> ans;
    void recurse(string s,int open,int close,int n){
        if(open==n and close==n){
            ans.push_back(s);
            return;
        }
        if(open<n)
            recurse(s+"(",open+1,close,n);
        if(close<open)
            recurse(s+")",open,close+1,n);
    }
    vector<string> generateParenthesis(int n) {
        recurse("",0,0,n);
        return ans;
    }
};

괄호 생성 Leetcode Java 솔루션:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    public void backtrack(List<String> list, String str, int open, int close, int max){
        if(str.length() == max*2){
            list.add(str);
            return;
        }        
        if(open < max){
            backtrack(list, str+"(", open+1, close, max);
        }
        if(close < open){
            backtrack(list, str+")", open, close+1, max);
        }
    }
}

괄호 생성을 위한 복잡성 분석 Leetcode 솔루션

시간 복잡성

위 코드의 시간 복잡성은 오(2^(2N)) 최악의 경우 N = 우리가 형성해야 하는 쌍의 수인 여는 대괄호와 닫는 대괄호의 모든 가능성을 고려해야 하기 때문입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. 의 위에). 

균열 시스템 설계 인터뷰
Translate »