首页 > 其他 > 详细

LeetCode 20 Generate Parentheses

时间:2015-05-10 17:13:59      阅读:204      评论:0      收藏:0      [点我收藏+]

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

还是类似的括号匹配问题,这次是要生成所有可能的匹配组合,思路如下:

首先用迭代法穷举可能出现的所有情况,然后利用已有的isValid()判断是否匹配,进而决定是否储存到返回vector容器中。

class Solution {
public:
    vector<string> generateParenthesis(int n) 
    {
        mSize = n * 2;
        init();
        string s;
        genpa(-1, s);
        return ret;
    }
    bool isValid(string s) 
{
    stack<char> stk;
    int nSize = s.size();

    for(int i = 0; i!= nSize; ++i)
    {
        if(s[i] == { || s[i] == ( || s[i]== [)
        {
            stk.push(s[i]);
        }
        else
        {
            if(stk.empty())
            {
                return false;
            }
            char cElem = stk.top();
            if(cElem - s[i] ==-1 || cElem - s[i] == -2)
            {
                stk.pop();
                continue;
            }
            else
            {
                return false;
            }
        }
    }
    if(!stk.empty())
    {
        return false;
    }
    return true;
}
    void genpa(int j, string s)
    {
        if(j == mSize -1)
        {
            if(isValid(s))
            {
                ret.push_back(s);
            }
            return;
        }
        for(int i = 0; i!= 2; ++i)
        {
            genpa(j+1, s+album[i]);
        }
    }
    void init(void)
    {
        album[0] = (;
        album[1] = );
    }
private:
    int mSize;
    vector<string> ret;
    char album[2];
};

思路类似,多举一反三。

LeetCode 20 Generate Parentheses

原文:http://www.cnblogs.com/bestwangjie/p/4492373.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!