Leetcode.22. Generate Parentheses

题目

有一对圆括号"()", 给定一个数字n,说明包含n对圆括号, 给出所有合法的可能.

Example:
input: [1, 0, -1, 0, -2, 2], 0.
output: [[-1,  0, 0, 1],[-2, -1, 1, 2],[-2,  0, 0, 2]]

思路1

递归, 合法字符串一定是先有"("再有")", 所以先写"(",当"("的个数大于")"时, 会写")".

代码简洁, 也容易理解, 但是很难想到啊.

void generateString(vector<string> &vec, string s, int left, int right) {
    if (left == 0 && right == 0) {
        vec.push_back(s);
        return;
    }

    if (left > 0) {
        generateString(vec, s+"(", left-1, right);
    }
    if (left < right) {
        generateString(vec, s+")", left, right-1);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    generateString(result, "", n, n);
    return result;
}

思路2

递归, 列出所有字符串情况, 然后验证是否合法. 思路比较简单, 但是速度慢, 对于递归来说速度和内存很致命.

bool isValid(string s) {
    int count = 0;
    for (char c : s) {
        if (count < 0) {
            return false;
        }
        if (c == '(') {
            count++;
        } else {
            count--;
        }
    }
    return count == 0;
}

void generateString(vector<string> &vec, string s, int left, int right) {
    if (left == 0 && right == 0) {
        if (isValid(s)) {
            vec.push_back(s);
        }
        return;
    }

    if (left > 0) {
        generateString(vec, s+"(", left-1, right);
    }
    if (right > 0) {
        generateString(vec, s+")", left, right-1);
    }

}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    generateString(result, "", n, n);
    return result;
}

总结

不定结果内容的使用递归比较容易理解.

寻求巧妙的递归.