LeetCode/Generate Parentheses.cpp at master · windshg/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// stupid solution
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string str = string(n, '(') + string(n, ')');
        do {
            if (valid(str)) ret.push_back(str);
        } while (next_permutation(str.begin(), str.end()));
        return ret;
    }

    inline bool valid(string &str) {
        int lpcount = 0;
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == '(') {
                lpcount ++;
            } else {
                if (lpcount > 0) -- lpcount;
                else return false;
            }
        }
        return true;
    }
};

// smarter method: DFS, which takes the shortest time.
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        dfs("", 0, 0, n, ret);
        return ret;
    }

    void dfs(string buf, int leftNum, int rightNum, const int n, vector<string> &ret) {
        if (rightNum > leftNum || leftNum > n) return;
        if (leftNum == rightNum && leftNum == n) {
            ret.push_back(buf);
            return;
        }
        dfs(buf + "(", leftNum + 1, rightNum, n, ret);
        dfs(buf + ")", leftNum, rightNum + 1, n, ret);
    }
};