荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
Generate valid pairs of paranthesis for a given input n.
()(),(()),..
Give DP solution.
Write Context Free grammar for it.
不是求个数,使打印组合
wwwyhx 发表于 2011-7-15 16:00 ![]()
用动态规划做比cracking code interview上的方法在时间上更高效
- void Combine(vector<string>& vecLft, vector<string>& vecRgt, vector<string>& vecRes)
- {
- vector<string>::iterator it1 = vecLft.begin();
- vector<string>::iterator it2 = vecRgt.begin();
- for (; it1 != vecLft.end(); it1++)
- for (; it2 != vecRgt.end(); it2++)
- {
- string str = *it1;
- str.insert(str.begin(), '(');
- str.insert(str.end(), ')');
- str += *it2;
- vecRes.push_back(str);
- }
- }
- void PrintNCombinations(int n)
- {
- assert (n > 0);
- vector<string>* pDP = new vector<string>[n+1];
- pDP[0].push_back("");
- for (int i = 1; i <= n; i++)
- {
- for (int j = 0; j < i; j++)
- {
- vector<string> vecTmp;
- Combine(pDP[j], pDP[i-1-j], vecTmp);
- pDP[i].insert(pDP[i].end(), vecTmp.begin(), vecTmp.end());
- }
- }
- vector<string>::iterator it = pDP[n].begin();
- for (; it != pDP[n].end(); it++)
- cout<<it->c_str()<<endl;
- delete []pDP;
- }
复制代码 |
|