C++LeetCode 구현(22.괄호 생 성)

[LeetCode]22.Parentheses 생 성 괄호
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
이 문 제 는 n 개의 괄호 가 있 는 모든 정확 한 형식 을 만 들 수 있 도록 숫자 n 을 지정 합 니 다.모든 결 과 를 보 여 주 는 문 제 는 우선 재 귀 Recursion 으로 풀 어야 합 니 다.문자열 은 왼쪽 괄호 와 오른쪽 괄호 두 글자 만 있 기 때문에 최종 결 과 는 반드시 왼쪽 괄호 3 개,오른쪽 괄호 3 개 입 니 다.따라서 여기 서 두 변 수 를 정의 합 니 다.left 와 right 는 각각 남 은 좌우 괄호 의 개 수 를 표시 합 니 다.만약 에 특정한 재 귀 할 때 왼쪽 괄호 의 개 수 는 오른쪽 괄호 의 개 수 보다 크 면 이때 생 성 된 문자열 에서 오른쪽 괄호 의 개 수 는 왼쪽 괄호 의 개수 보다 크 면')('이런 불법 문자열 이 나타 날 수 있 기 때문에 이런 상황 은 바로 돌아 가 고 계속 처리 하지 않 습 니 다.만약 left 와 right 가 모두 0 이 라면,이때 생 성 된 문자열 은 3 개의 왼쪽 괄호 와 3 개의 오른쪽 괄호 가 있 고,문자열 이 합 법 적 이 며,결과 에 저장 한 후에 되 돌아 온 다 는 것 을 설명 합 니 다.만약 에 상기 두 가지 상황 이 모두 만족 하지 않 으 면 이때 left 가 0 보다 크 면 재 귀 함 수 를 호출 하고 매개 변수의 업데이트 에 주의 하 며 right 가 0 보다 크 면 재 귀 함 수 를 호출 합 니 다.똑 같이 파 라 메 터 를 업데이트 해 야 합 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        generateParenthesisDFS(n, n, "", res);
        return res;
    }
    void generateParenthesisDFS(int left, int right, string out, vector<string> &res) {
        if (left > right) return;
        if (left == 0 && right == 0) res.push_back(out);
        else {
            if (left > 0) generateParenthesisDFS(left - 1, right, out + '(', res);
            if (right > 0) generateParenthesisDFS(left, right - 1, out + ')', res);
        }
    }
};

자바 해법 1:

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        helper(n, n, "", res);
        return res;
    }
    void helper(int left, int right, String out, List<String> res) {
        if (left < 0 || right < 0 || left > right) return;
        if (left == 0 && right == 0) {
            res.add(out);
            return;
        }
        helper(left - 1, right, out + "(", res);
        helper(left, right - 1, out + ")", res);
    }
}

그 방법 을 살 펴 보면 이런 방법 은 CareerCup 책 에서 주 는 방법 이 고 느낌 도 교묘 한 방법 이다.이런 방법 은 왼쪽 괄호 를 찾 는 것 이다.왼쪽 괄호 를 찾 을 때마다 그 뒤에 완전한 괄호 를 추가 하고 마지막 에 처음에()를 추가 하면 모든 상황 이 형성 된다.주의해 야 할 것 은 가끔 반복 되 는 상황 이 발생 할 수 있다 는 것 이다.따라서 set 데이터 구 조 를 사용 하면 중복 항목 이 발생 하면 결과 에 가입 하지 않 고 마지막 으로 set 를 vector 로 바 꾸 면 됩 니 다.코드 는 다음 과 같 습 니 다.
n＝1:    ()
n=2:    (())    ()()
n=3:    (()())    ((()))    ()(())    (())()    ()()()   
C++해법 2:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        unordered_set<string> st;
        if (n == 0) st.insert("");
        else {
            vector<string> pre = generateParenthesis(n - 1);
            for (auto a : pre) {
                for (int i = 0; i < a.size(); ++i) {
                    if (a[i] == '(') {
                        a.insert(a.begin() + i + 1, '(');
                        a.insert(a.begin() + i + 2, ')');
                        st.insert(a);
                        a.erase(a.begin() + i + 1, a.begin() + i + 3);
                    }
                }
                st.insert("()" + a);
            }
        }
        return vector<string>(st.begin(), st.end());
    }
};

자바 해법 2:

public class Solution {
    public List<String> generateParenthesis(int n) {
        Set<String> res = new HashSet<String>();
        if (n == 0) {
            res.add("");
        } else {
            List<String> pre = generateParenthesis(n - 1);
            for (String str : pre) {
                for (int i = 0; i < str.length(); ++i) {
                    if (str.charAt(i) == '(') {
                        str = str.substring(0, i + 1) + "()" + str.substring(i + 1, str.length());
                        res.add(str);
                        str = str.substring(0, i + 1) +  str.substring(i + 3, str.length());
                    }
                }
                res.add("()" + str);
            }
        }
        return new ArrayList(res);
    }
}

여기 서 C++구현 LeetCode(22.괄호 생 성)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 생 성 괄호 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!